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