1 /**
2  * libdmtx - Data Matrix Encoding/Decoding Library
3  * Copyright 2011 Mike Laughton. All rights reserved.
4  * Copyright 2012-2016 Vadim A. Misbakh-Soloviov. All rights reserved.
5  *
6  * See LICENSE file in the main project directory for full
7  * terms of use and distribution.
8  *
9  * Contact:
10  * Vadim A. Misbakh-Soloviov <dmtx@mva.name>
11  * Mike Laughton <mike@dragonflylogic.com>
12  *
13  * \file dmtxencodeoptimize.c
14  * \brief Logic for optimized (multiple scheme) encoding
15  */
16 
17 #define DUMPSTREAMS 0
18 
19 enum SchemeState {
20    AsciiFull,
21    AsciiCompactOffset0, /* 0 offset from first regular input value */
22    AsciiCompactOffset1,
23    C40Offset0,          /* 0 offset from first expanded C40 value */
24    C40Offset1,
25    C40Offset2,
26    TextOffset0,         /* 0 offset from first expanded Text value */
27    TextOffset1,
28    TextOffset2,
29    X12Offset0,          /* 0 offset from first expanded X12 value */
30    X12Offset1,
31    X12Offset2,
32    EdifactOffset0,      /* 0 offset from first regular input value */
33    EdifactOffset1,
34    EdifactOffset2,
35    EdifactOffset3,
36    Base256,
37    SchemeStateCount
38 };
39 
40 #if DUMPSTREAMS
DumpStreams(DmtxEncodeStream * streamBest)41 static void DumpStreams(DmtxEncodeStream *streamBest)
42 {
43    enum SchemeState state;
44    char prefix[32];
45 
46    fprintf(stdout, "----------------------------------------\n");
47    for(state = 0; state < SchemeStateCount; state++)
48    {
49       if(streamBest[state].status == DmtxStatusEncoding ||
50             streamBest[state].status == DmtxStatusComplete)
51          fprintf(stdout, "\"%c\" ", streamBest[state].input->b[streamBest[state].inputNext-1]);
52       else
53          fprintf(stdout, "    ");
54 
55       switch(streamBest[state].status) {
56          case DmtxStatusEncoding:
57             snprintf(prefix, sizeof(prefix), "%2d (%s): ", state, " encode ");
58             break;
59          case DmtxStatusComplete:
60             snprintf(prefix, sizeof(prefix), "%2d (%s): ", state, "complete");
61             break;
62          case DmtxStatusInvalid:
63             snprintf(prefix, sizeof(prefix), "%2d (%s): ", state, "invalid ");
64             break;
65          case DmtxStatusFatal:
66             snprintf(prefix, sizeof(prefix), "%2d (%s): ", state, " fatal  ");
67             break;
68       }
69       dmtxByteListPrint(streamBest[state].output, prefix);
70    }
71 }
72 #endif
73 
74 
75 /**
76  *
77  *
78  */
79 static int
EncodeOptimizeBest(DmtxByteList * input,DmtxByteList * output,int sizeIdxRequest,int fnc1)80 EncodeOptimizeBest(DmtxByteList *input, DmtxByteList *output, int sizeIdxRequest, int fnc1)
81 {
82    enum SchemeState state;
83    int inputNext, c40ValueCount, textValueCount, x12ValueCount;
84    int sizeIdx;
85    DmtxEncodeStream *winner;
86    DmtxPassFail passFail;
87    DmtxEncodeStream streamsBest[SchemeStateCount];
88    DmtxEncodeStream streamsTemp[SchemeStateCount];
89    DmtxByte outputsBestStorage[SchemeStateCount][4096];
90    DmtxByte outputsTempStorage[SchemeStateCount][4096];
91    DmtxByte ctxTempStorage[4];
92    DmtxByteList outputsBest[SchemeStateCount];
93    DmtxByteList outputsTemp[SchemeStateCount];
94    DmtxByteList ctxTemp = dmtxByteListBuild(ctxTempStorage, sizeof(ctxTempStorage));
95 
96    /* Initialize all streams with their own output storage */
97    for(state = 0; state < SchemeStateCount; state++)
98    {
99       outputsBest[state] = dmtxByteListBuild(outputsBestStorage[state], sizeof(outputsBestStorage[state]));
100       outputsTemp[state] = dmtxByteListBuild(outputsTempStorage[state], sizeof(outputsTempStorage[state]));
101       streamsBest[state] = StreamInit(input, &(outputsBest[state]));
102       streamsTemp[state] = StreamInit(input, &(outputsTemp[state]));
103       streamsBest[state].fnc1 = fnc1;
104       streamsTemp[state].fnc1 = fnc1;
105    }
106 
107    c40ValueCount = textValueCount = x12ValueCount = 0;
108 
109    for(inputNext = 0; inputNext < input->length; inputNext++)
110    {
111       StreamAdvanceFromBest(streamsTemp, streamsBest, AsciiFull, sizeIdxRequest);
112 
113       AdvanceAsciiCompact(streamsTemp, streamsBest, AsciiCompactOffset0, inputNext, sizeIdxRequest);
114       AdvanceAsciiCompact(streamsTemp, streamsBest, AsciiCompactOffset1, inputNext, sizeIdxRequest);
115 
116       AdvanceCTX(streamsTemp, streamsBest, C40Offset0, inputNext, c40ValueCount, sizeIdxRequest);
117       AdvanceCTX(streamsTemp, streamsBest, C40Offset1, inputNext, c40ValueCount, sizeIdxRequest);
118       AdvanceCTX(streamsTemp, streamsBest, C40Offset2, inputNext, c40ValueCount, sizeIdxRequest);
119 
120       AdvanceCTX(streamsTemp, streamsBest, TextOffset0, inputNext, textValueCount, sizeIdxRequest);
121       AdvanceCTX(streamsTemp, streamsBest, TextOffset1, inputNext, textValueCount, sizeIdxRequest);
122       AdvanceCTX(streamsTemp, streamsBest, TextOffset2, inputNext, textValueCount, sizeIdxRequest);
123 
124       AdvanceCTX(streamsTemp, streamsBest, X12Offset0, inputNext, x12ValueCount, sizeIdxRequest);
125       AdvanceCTX(streamsTemp, streamsBest, X12Offset1, inputNext, x12ValueCount, sizeIdxRequest);
126       AdvanceCTX(streamsTemp, streamsBest, X12Offset2, inputNext, x12ValueCount, sizeIdxRequest);
127 
128       AdvanceEdifact(streamsTemp, streamsBest, EdifactOffset0, inputNext, sizeIdxRequest);
129       AdvanceEdifact(streamsTemp, streamsBest, EdifactOffset1, inputNext, sizeIdxRequest);
130       AdvanceEdifact(streamsTemp, streamsBest, EdifactOffset2, inputNext, sizeIdxRequest);
131       AdvanceEdifact(streamsTemp, streamsBest, EdifactOffset3, inputNext, sizeIdxRequest);
132 
133       StreamAdvanceFromBest(streamsTemp, streamsBest, Base256, sizeIdxRequest);
134 
135       /* Overwrite best streams with new results */
136       for(state = 0; state < SchemeStateCount; state++)
137       {
138          if(streamsBest[state].status != DmtxStatusComplete)
139             StreamCopy(&(streamsBest[state]), &(streamsTemp[state]));
140       }
141 
142       dmtxByteListClear(&ctxTemp);
143       PushCTXValues(&ctxTemp, input->b[inputNext], DmtxSchemeC40, &passFail, fnc1);
144       c40ValueCount += ((passFail == DmtxPass) ? ctxTemp.length : 1);
145 
146       dmtxByteListClear(&ctxTemp);
147       PushCTXValues(&ctxTemp, input->b[inputNext], DmtxSchemeText, &passFail, fnc1);
148       textValueCount += ((passFail == DmtxPass) ? ctxTemp.length : 1);
149 
150       dmtxByteListClear(&ctxTemp);
151       PushCTXValues(&ctxTemp, input->b[inputNext], DmtxSchemeX12, &passFail, fnc1);
152       x12ValueCount += ((passFail == DmtxPass) ? ctxTemp.length : 1);
153 
154 #if DUMPSTREAMS
155       DumpStreams(streamsBest);
156 #endif
157    }
158 
159    /* Choose the overall winner */
160    winner = NULL;
161    for(state = 0; state < SchemeStateCount; state++)
162    {
163       if(streamsBest[state].status == DmtxStatusComplete)
164       {
165          if(winner == NULL || streamsBest[state].output->length < winner->output->length)
166             winner = &(streamsBest[state]);
167       }
168    }
169 
170    /* Copy winner to output */
171    if(winner == NULL)
172    {
173       sizeIdx = DmtxUndefined;
174    }
175    else
176    {
177       dmtxByteListCopy(output, winner->output, &passFail);
178       sizeIdx = (passFail == DmtxPass) ? winner->sizeIdx : DmtxUndefined;
179    }
180 
181    return sizeIdx;
182 }
183 
184 /**
185  * It's safe to compare output length because all targetState combinations
186  * start on same input and encodes same number of inputs. Only difference
187  * is the number of latches/unlatches that are also encoded
188  */
189 static void
StreamAdvanceFromBest(DmtxEncodeStream * streamsNext,DmtxEncodeStream * streamsBest,int targetState,int sizeIdxRequest)190 StreamAdvanceFromBest(DmtxEncodeStream *streamsNext, DmtxEncodeStream *streamsBest,
191      int targetState, int sizeIdxRequest)
192 {
193    enum SchemeState fromState;
194    DmtxScheme targetScheme;
195    DmtxEncodeOption encodeOption;
196    DmtxByte outputTempStorage[4096];
197    DmtxByteList outputTemp = dmtxByteListBuild(outputTempStorage, sizeof(outputTempStorage));
198    DmtxEncodeStream streamTemp;
199    DmtxEncodeStream *targetStream = &(streamsNext[targetState]);
200 
201    streamTemp.output = &outputTemp; /* Set directly instead of calling StreamInit() */
202    targetScheme = GetScheme(targetState);
203 
204    if(targetState == AsciiFull)
205       encodeOption = DmtxEncodeFull;
206    else if(targetState == AsciiCompactOffset0 || targetState == AsciiCompactOffset1)
207       encodeOption = DmtxEncodeCompact;
208    else
209       encodeOption = DmtxEncodeNormal;
210 
211    for(fromState = 0; fromState < SchemeStateCount; fromState++)
212    {
213       if(streamsBest[fromState].status != DmtxStatusEncoding ||
214             ValidStateSwitch(fromState, targetState) == DmtxFalse)
215       {
216          continue;
217       }
218 
219       StreamCopy(&streamTemp, &(streamsBest[fromState]));
220       EncodeNextChunk(&streamTemp, targetScheme, encodeOption, sizeIdxRequest);
221 
222       if(fromState == 0 || (streamTemp.status != DmtxStatusInvalid &&
223             streamTemp.output->length < targetStream->output->length))
224       {
225          StreamCopy(targetStream, &streamTemp);
226       }
227    }
228 }
229 
230 /**
231  *
232  */
233 static void
AdvanceAsciiCompact(DmtxEncodeStream * streamsNext,DmtxEncodeStream * streamsBest,int targetState,int inputNext,int sizeIdxRequest)234 AdvanceAsciiCompact(DmtxEncodeStream *streamsNext, DmtxEncodeStream *streamsBest,
235       int targetState, int inputNext, int sizeIdxRequest)
236 {
237    DmtxEncodeStream *currentStream = &(streamsBest[targetState]);
238    DmtxEncodeStream *targetStream = &(streamsNext[targetState]);
239    DmtxBoolean isStartState;
240 
241    switch(targetState)
242    {
243       case AsciiCompactOffset0:
244          isStartState = (inputNext % 2 == 0) ? DmtxTrue : DmtxFalse;
245          break;
246 
247       case AsciiCompactOffset1:
248          isStartState = (inputNext % 2 == 1) ? DmtxTrue : DmtxFalse;
249          break;
250 
251       default:
252          StreamMarkFatal(targetStream, DmtxErrorIllegalParameterValue);
253          return;
254    }
255 
256    if(inputNext < currentStream->inputNext)
257    {
258       StreamCopy(targetStream, currentStream);
259    }
260    else if(isStartState == DmtxTrue)
261    {
262       StreamAdvanceFromBest(streamsNext, streamsBest, targetState, sizeIdxRequest);
263    }
264    else
265    {
266       StreamCopy(targetStream, currentStream);
267       StreamMarkInvalid(targetStream, DmtxErrorUnknown);
268    }
269 }
270 
271 /**
272  *
273  */
274 static void
AdvanceCTX(DmtxEncodeStream * streamsNext,DmtxEncodeStream * streamsBest,int targetState,int inputNext,int ctxValueCount,int sizeIdxRequest)275 AdvanceCTX(DmtxEncodeStream *streamsNext, DmtxEncodeStream *streamsBest,
276       int targetState, int inputNext, int ctxValueCount, int sizeIdxRequest)
277 {
278    DmtxEncodeStream *currentStream = &(streamsBest[targetState]);
279    DmtxEncodeStream *targetStream = &(streamsNext[targetState]);
280    DmtxBoolean isStartState;
281 
282    /* we won't actually use inputNext here */
283    switch(targetState)
284    {
285       case C40Offset0:
286       case TextOffset0:
287       case X12Offset0:
288          isStartState = (ctxValueCount % 3 == 0) ? DmtxTrue : DmtxFalse;
289          break;
290 
291       case C40Offset1:
292       case TextOffset1:
293       case X12Offset1:
294          isStartState = (ctxValueCount % 3 == 1) ? DmtxTrue : DmtxFalse;
295          break;
296 
297       case C40Offset2:
298       case TextOffset2:
299       case X12Offset2:
300          isStartState = (ctxValueCount % 3 == 2) ? DmtxTrue : DmtxFalse;
301          break;
302 
303       default:
304          StreamMarkFatal(targetStream, DmtxErrorIllegalParameterValue);
305          return;
306    }
307 
308    if(inputNext < currentStream->inputNext)
309    {
310       StreamCopy(targetStream, currentStream);
311    }
312    else if(isStartState == DmtxTrue)
313    {
314       StreamAdvanceFromBest(streamsNext, streamsBest, targetState, sizeIdxRequest);
315    }
316    else
317    {
318       StreamCopy(targetStream, currentStream);
319       StreamMarkInvalid(targetStream, DmtxErrorUnknown);
320    }
321 }
322 
323 /**
324  *
325  */
326 static void
AdvanceEdifact(DmtxEncodeStream * streamsNext,DmtxEncodeStream * streamsBest,int targetState,int inputNext,int sizeIdxRequest)327 AdvanceEdifact(DmtxEncodeStream *streamsNext, DmtxEncodeStream *streamsBest,
328       int targetState, int inputNext, int sizeIdxRequest)
329 {
330    DmtxEncodeStream *currentStream = &(streamsBest[targetState]);
331    DmtxEncodeStream *targetStream = &(streamsNext[targetState]);
332    DmtxBoolean isStartState;
333 
334    switch(targetState)
335    {
336       case EdifactOffset0:
337          isStartState = (inputNext % 4 == 0) ? DmtxTrue : DmtxFalse;
338          break;
339 
340       case EdifactOffset1:
341          isStartState = (inputNext % 4 == 1) ? DmtxTrue : DmtxFalse;
342          break;
343 
344       case EdifactOffset2:
345          isStartState = (inputNext % 4 == 2) ? DmtxTrue : DmtxFalse;
346          break;
347 
348       case EdifactOffset3:
349          isStartState = (inputNext % 4 == 3) ? DmtxTrue : DmtxFalse;
350          break;
351 
352       default:
353          StreamMarkFatal(targetStream, DmtxErrorIllegalParameterValue);
354          return;
355    }
356 
357    if(isStartState == DmtxTrue)
358    {
359       StreamAdvanceFromBest(streamsNext, streamsBest, targetState, sizeIdxRequest);
360    }
361    else
362    {
363       StreamCopy(targetStream, currentStream);
364       if(currentStream->status == DmtxStatusEncoding && currentStream->currentScheme == DmtxSchemeEdifact)
365          EncodeNextChunk(targetStream, DmtxSchemeEdifact, DmtxEncodeNormal, sizeIdxRequest);
366       else
367          StreamMarkInvalid(targetStream, DmtxErrorUnknown);
368    }
369 }
370 
371 /**
372  *
373  *
374  */
375 static int
GetScheme(int state)376 GetScheme(int state)
377 {
378    DmtxScheme scheme;
379 
380    switch(state)
381    {
382       case AsciiFull:
383       case AsciiCompactOffset0:
384       case AsciiCompactOffset1:
385          scheme = DmtxSchemeAscii;
386          break;
387       case C40Offset0:
388       case C40Offset1:
389       case C40Offset2:
390          scheme = DmtxSchemeC40;
391          break;
392       case TextOffset0:
393       case TextOffset1:
394       case TextOffset2:
395          scheme = DmtxSchemeText;
396          break;
397       case X12Offset0:
398       case X12Offset1:
399       case X12Offset2:
400          scheme = DmtxSchemeX12;
401          break;
402       case EdifactOffset0:
403       case EdifactOffset1:
404       case EdifactOffset2:
405       case EdifactOffset3:
406          scheme = DmtxSchemeEdifact;
407          break;
408       case Base256:
409          scheme = DmtxSchemeBase256;
410          break;
411       default:
412          scheme = DmtxUndefined;
413          break;
414    }
415 
416    return scheme;
417 }
418 
419 /**
420  *
421  *
422  */
423 static DmtxBoolean
ValidStateSwitch(int fromState,int targetState)424 ValidStateSwitch(int fromState, int targetState)
425 {
426    DmtxBoolean validStateSwitch;
427    DmtxScheme fromScheme = GetScheme(fromState);
428    DmtxScheme toScheme = GetScheme(targetState);
429 
430    if(fromScheme == toScheme && fromState != targetState &&
431          fromState != AsciiFull && targetState != AsciiFull)
432    {
433       validStateSwitch = DmtxFalse;
434    }
435    else
436    {
437       validStateSwitch = DmtxTrue;
438    }
439 
440    return validStateSwitch;
441 }
442