1 /** 2 * libdmtx - Data Matrix Encoding/Decoding Library 3 * Copyright 2008, 2009 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 dmtxstatic.h 14 * \brief Static header 15 */ 16 17 #ifndef __DMTXSTATIC_H__ 18 #define __DMTXSTATIC_H__ 19 20 #define DmtxAlmostZero 0.000001 21 #define DmtxAlmostInfinity -1 22 23 #define DmtxValueC40Latch 230 24 #define DmtxValueTextLatch 239 25 #define DmtxValueX12Latch 238 26 #define DmtxValueEdifactLatch 240 27 #define DmtxValueBase256Latch 231 28 29 #define DmtxValueCTXUnlatch 254 30 #define DmtxValueEdifactUnlatch 31 31 32 #define DmtxValueAsciiPad 129 33 #define DmtxValueAsciiUpperShift 235 34 #define DmtxValueCTXShift1 0 35 #define DmtxValueCTXShift2 1 36 #define DmtxValueCTXShift3 2 37 #define DmtxValueFNC1 232 38 #define DmtxValueStructuredAppend 233 39 #define DmtxValueReaderProgramming 234 40 #define DmtxValue05Macro 236 41 #define DmtxValue06Macro 237 42 #define DmtxValueECI 241 43 44 #define DmtxC40TextBasicSet 0 45 #define DmtxC40TextShift1 1 46 #define DmtxC40TextShift2 2 47 #define DmtxC40TextShift3 3 48 49 #define DmtxUnlatchExplicit 0 50 #define DmtxUnlatchImplicit 1 51 52 #define DmtxChannelValid 0x00 53 #define DmtxChannelUnsupportedChar 0x01 << 0 54 #define DmtxChannelCannotUnlatch 0x01 << 1 55 56 #undef min 57 #define min(X,Y) (((X) < (Y)) ? (X) : (Y)) 58 59 #undef max 60 #define max(X,Y) (((X) > (Y)) ? (X) : (Y)) 61 62 typedef enum { 63 DmtxEncodeNormal, /* Use normal scheme behavior (e.g., ASCII auto) */ 64 DmtxEncodeCompact, /* Use only compact format within scheme */ 65 DmtxEncodeFull /* Use only fully expanded format within scheme */ 66 } DmtxEncodeOption; 67 68 typedef enum { 69 DmtxRangeGood, 70 DmtxRangeBad, 71 DmtxRangeEnd 72 } DmtxRange; 73 74 typedef enum { 75 DmtxEdgeTop = 0x01 << 0, 76 DmtxEdgeBottom = 0x01 << 1, 77 DmtxEdgeLeft = 0x01 << 2, 78 DmtxEdgeRight = 0x01 << 3 79 } DmtxEdge; 80 81 typedef enum { 82 DmtxMaskBit8 = 0x01 << 0, 83 DmtxMaskBit7 = 0x01 << 1, 84 DmtxMaskBit6 = 0x01 << 2, 85 DmtxMaskBit5 = 0x01 << 3, 86 DmtxMaskBit4 = 0x01 << 4, 87 DmtxMaskBit3 = 0x01 << 5, 88 DmtxMaskBit2 = 0x01 << 6, 89 DmtxMaskBit1 = 0x01 << 7 90 } DmtxMaskBit; 91 92 /** 93 * @struct DmtxFollow 94 * @brief DmtxFollow 95 */ 96 typedef struct DmtxFollow_struct { 97 unsigned char *ptr; 98 unsigned char neighbor; 99 int step; 100 DmtxPixelLoc loc; 101 } DmtxFollow; 102 103 /** 104 * @struct DmtxBresLine 105 * @brief DmtxBresLine 106 */ 107 typedef struct DmtxBresLine_struct { 108 int xStep; 109 int yStep; 110 int xDelta; 111 int yDelta; 112 int steep; 113 int xOut; 114 int yOut; 115 int travel; 116 int outward; 117 int error; 118 DmtxPixelLoc loc; 119 DmtxPixelLoc loc0; 120 DmtxPixelLoc loc1; 121 } DmtxBresLine; 122 123 typedef struct C40TextState_struct { 124 int shift; 125 DmtxBoolean upperShift; 126 } C40TextState; 127 128 /* dmtxregion.c */ 129 static double RightAngleTrueness(DmtxVector2 c0, DmtxVector2 c1, DmtxVector2 c2, double angle); 130 static DmtxPointFlow MatrixRegionSeekEdge(DmtxDecode *dec, DmtxPixelLoc loc0); 131 static DmtxPassFail MatrixRegionOrientation(DmtxDecode *dec, DmtxRegion *reg, DmtxPointFlow flowBegin); 132 static long DistanceSquared(DmtxPixelLoc a, DmtxPixelLoc b); 133 static int ReadModuleColor(DmtxDecode *dec, DmtxRegion *reg, int symbolRow, int symbolCol, int sizeIdx, int colorPlane); 134 135 static DmtxPassFail MatrixRegionFindSize(DmtxDecode *dec, DmtxRegion *reg); 136 static int CountJumpTally(DmtxDecode *dec, DmtxRegion *reg, int xStart, int yStart, DmtxDirection dir); 137 static DmtxPointFlow GetPointFlow(DmtxDecode *dec, int colorPlane, DmtxPixelLoc loc, int arrive); 138 static DmtxPointFlow FindStrongestNeighbor(DmtxDecode *dec, DmtxPointFlow center, int sign); 139 static DmtxFollow FollowSeek(DmtxDecode *dec, DmtxRegion *reg, int seek); 140 static DmtxFollow FollowSeekLoc(DmtxDecode *dec, DmtxPixelLoc loc); 141 static DmtxFollow FollowStep(DmtxDecode *dec, DmtxRegion *reg, DmtxFollow followBeg, int sign); 142 static DmtxFollow FollowStep2(DmtxDecode *dec, DmtxFollow followBeg, int sign); 143 static DmtxPassFail TrailBlazeContinuous(DmtxDecode *dec, DmtxRegion *reg, DmtxPointFlow flowBegin, int maxDiagonal); 144 static int TrailBlazeGapped(DmtxDecode *dec, DmtxRegion *reg, DmtxBresLine line, int streamDir); 145 static int TrailClear(DmtxDecode *dec, DmtxRegion *reg, int clearMask); 146 static DmtxBestLine FindBestSolidLine(DmtxDecode *dec, DmtxRegion *reg, int step0, int step1, int streamDir, int houghAvoid); 147 static DmtxBestLine FindBestSolidLine2(DmtxDecode *dec, DmtxPixelLoc loc0, int tripSteps, int sign, int houghAvoid); 148 static DmtxPassFail FindTravelLimits(DmtxDecode *dec, DmtxRegion *reg, DmtxBestLine *line); 149 static DmtxPassFail MatrixRegionAlignCalibEdge(DmtxDecode *dec, DmtxRegion *reg, int whichEdge); 150 static DmtxBresLine BresLineInit(DmtxPixelLoc loc0, DmtxPixelLoc loc1, DmtxPixelLoc locInside); 151 static DmtxPassFail BresLineGetStep(DmtxBresLine line, DmtxPixelLoc target, int *travel, int *outward); 152 static DmtxPassFail BresLineStep(DmtxBresLine *line, int travel, int outward); 153 /*static void WriteDiagnosticImage(DmtxDecode *dec, DmtxRegion *reg, char *imagePath);*/ 154 155 /* dmtxdecode.c */ 156 static void TallyModuleJumps(DmtxDecode *dec, DmtxRegion *reg, int tally[][24], int xOrigin, int yOrigin, int mapWidth, int mapHeight, DmtxDirection dir); 157 static DmtxPassFail PopulateArrayFromMatrix(DmtxDecode *dec, DmtxRegion *reg, DmtxMessage *msg); 158 159 /* dmtxdecodescheme.c */ 160 static void DecodeDataStream(DmtxMessage *msg, int sizeIdx, unsigned char *outputStart); 161 static int GetEncodationScheme(unsigned char cw); 162 static void PushOutputWord(DmtxMessage *msg, int value); 163 static void PushOutputC40TextWord(DmtxMessage *msg, C40TextState *state, int value); 164 static void PushOutputMacroHeader(DmtxMessage *msg, int macroType); 165 static void PushOutputMacroTrailer(DmtxMessage *msg); 166 static unsigned char *DecodeSchemeAscii(DmtxMessage *msg, unsigned char *ptr, unsigned char *dataEnd); 167 static unsigned char *DecodeSchemeC40Text(DmtxMessage *msg, unsigned char *ptr, unsigned char *dataEnd, DmtxScheme encScheme); 168 static unsigned char *DecodeSchemeX12(DmtxMessage *msg, unsigned char *ptr, unsigned char *dataEnd); 169 static unsigned char *DecodeSchemeEdifact(DmtxMessage *msg, unsigned char *ptr, unsigned char *dataEnd); 170 static unsigned char *DecodeSchemeBase256(DmtxMessage *msg, unsigned char *ptr, unsigned char *dataEnd); 171 172 /* dmtxencode.c */ 173 static void PrintPattern(DmtxEncode *encode); 174 static int EncodeDataCodewords(DmtxByteList *input, DmtxByteList *output, int sizeIdxRequest, DmtxScheme scheme, int fnc1); 175 176 /* dmtxplacemod.c */ 177 static int ModulePlacementEcc200(unsigned char *modules, unsigned char *codewords, int sizeIdx, int moduleOnColor); 178 static void PatternShapeStandard(unsigned char *modules, int mappingRows, int mappingCols, int row, int col, unsigned char *codeword, int moduleOnColor); 179 static void PatternShapeSpecial1(unsigned char *modules, int mappingRows, int mappingCols, unsigned char *codeword, int moduleOnColor); 180 static void PatternShapeSpecial2(unsigned char *modules, int mappingRows, int mappingCols, unsigned char *codeword, int moduleOnColor); 181 static void PatternShapeSpecial3(unsigned char *modules, int mappingRows, int mappingCols, unsigned char *codeword, int moduleOnColor); 182 static void PatternShapeSpecial4(unsigned char *modules, int mappingRows, int mappingCols, unsigned char *codeword, int moduleOnColor); 183 static void PlaceModule(unsigned char *modules, int mappingRows, int mappingCols, int row, int col, 184 unsigned char *codeword, int mask, int moduleOnColor); 185 186 /* dmtxreedsol.c */ 187 static DmtxPassFail RsEncode(DmtxMessage *message, int sizeIdx); 188 static DmtxPassFail RsDecode(unsigned char *code, int sizeIdx, int fix); 189 static DmtxPassFail RsGenPoly(DmtxByteList *gen, int errorWordCount); 190 static DmtxBoolean RsComputeSyndromes(DmtxByteList *syn, const DmtxByteList *rec, int blockErrorWords); 191 static DmtxBoolean RsFindErrorLocatorPoly(DmtxByteList *elp, const DmtxByteList *syn, int errorWordCount, int maxCorrectable); 192 static DmtxBoolean RsFindErrorLocations(DmtxByteList *loc, const DmtxByteList *elp); 193 static DmtxPassFail RsRepairErrors(DmtxByteList *rec, const DmtxByteList *loc, const DmtxByteList *elp, const DmtxByteList *syn); 194 195 /* dmtxscangrid.c */ 196 static DmtxScanGrid InitScanGrid(DmtxDecode *dec); 197 static int PopGridLocation(DmtxScanGrid *grid, /*@out@*/ DmtxPixelLoc *locPtr); 198 static int GetGridCoordinates(DmtxScanGrid *grid, /*@out@*/ DmtxPixelLoc *locPtr); 199 static void SetDerivedFields(DmtxScanGrid *grid); 200 201 /* dmtxsymbol.c */ 202 static int FindSymbolSize(int dataWords, int sizeIdxRequest); 203 204 /* dmtximage.c */ 205 static int GetBitsPerPixel(int pack); 206 207 /* dmtxencodestream.c */ 208 static DmtxEncodeStream StreamInit(DmtxByteList *input, DmtxByteList *output); 209 static void StreamCopy(DmtxEncodeStream *dst, DmtxEncodeStream *src); 210 static void StreamMarkComplete(DmtxEncodeStream *stream, int sizeIdx); 211 static void StreamMarkInvalid(DmtxEncodeStream *stream, int reasonIdx); 212 static void StreamMarkFatal(DmtxEncodeStream *stream, int reasonIdx); 213 static void StreamOutputChainAppend(DmtxEncodeStream *stream, DmtxByte value); 214 static DmtxByte StreamOutputChainRemoveLast(DmtxEncodeStream *stream); 215 static void StreamOutputSet(DmtxEncodeStream *stream, int index, DmtxByte value); 216 static DmtxBoolean StreamInputHasNext(DmtxEncodeStream *stream); 217 static DmtxByte StreamInputPeekNext(DmtxEncodeStream *stream); 218 static DmtxByte StreamInputAdvanceNext(DmtxEncodeStream *stream); 219 static void StreamInputAdvancePrev(DmtxEncodeStream *stream); 220 221 /* dmtxencodescheme.c */ 222 static int EncodeSingleScheme(DmtxByteList *input, DmtxByteList *output, int sizeIdxRequest, DmtxScheme scheme, int fnc1); 223 static void EncodeNextChunk(DmtxEncodeStream *stream, int scheme, int subScheme, int sizeIdxRequest); 224 static void EncodeChangeScheme(DmtxEncodeStream *stream, DmtxScheme targetScheme, int unlatchType); 225 static int GetRemainingSymbolCapacity(int outputLength, int sizeIdx); 226 227 /* dmtxencodeoptimize.c */ 228 static int EncodeOptimizeBest(DmtxByteList *input, DmtxByteList *output, int sizeIdxRequest, int fnc1); 229 static void StreamAdvanceFromBest(DmtxEncodeStream *streamNext, 230 DmtxEncodeStream *streamList, int targeteState, int sizeIdxRequest); 231 static void AdvanceAsciiCompact(DmtxEncodeStream *streamNext, DmtxEncodeStream *streamList, 232 int state, int inputNext, int sizeIdxRequest); 233 static void AdvanceCTX(DmtxEncodeStream *streamNext, DmtxEncodeStream *streamList, 234 int state, int inputNext, int ctxValueCount, int sizeIdxRequest); 235 static void AdvanceEdifact(DmtxEncodeStream *streamNext, DmtxEncodeStream *streamList, 236 int state, int inputNext, int sizeIdxRequest); 237 static int GetScheme(int state); 238 static DmtxBoolean ValidStateSwitch(int fromState, int targetState); 239 240 /* dmtxencodeascii.c */ 241 static void EncodeNextChunkAscii(DmtxEncodeStream *stream, int option); 242 static void AppendValueAscii(DmtxEncodeStream *stream, DmtxByte value); 243 static void CompleteIfDoneAscii(DmtxEncodeStream *stream, int sizeIdxRequest); 244 static void PadRemainingInAscii(DmtxEncodeStream *stream, int sizeIdx); 245 static DmtxByteList EncodeTmpRemainingInAscii(DmtxEncodeStream *stream, DmtxByte *storage, int capacity, DmtxPassFail *passFail); 246 static DmtxByte Randomize253State(DmtxByte cwValue, int cwPosition); 247 248 /* dmtxencodec40textx12.c */ 249 static void EncodeNextChunkCTX(DmtxEncodeStream *stream, int sizeIdxRequest); 250 static void AppendValuesCTX(DmtxEncodeStream *stream, DmtxByteList *valueList); 251 static void AppendUnlatchCTX(DmtxEncodeStream *stream); 252 static void CompleteIfDoneCTX(DmtxEncodeStream *stream, int sizeIdxRequest); 253 static void CompletePartialC40Text(DmtxEncodeStream *stream, DmtxByteList *valueList, int sizeIdxRequest); 254 static void CompletePartialX12(DmtxEncodeStream *stream, DmtxByteList *valueList, int sizeIdxRequest); 255 static DmtxBoolean PartialX12ChunkRemains(DmtxEncodeStream *stream); 256 static void PushCTXValues(DmtxByteList *valueList, DmtxByte inputValue, int targetScheme, DmtxPassFail *passFail, int fnc1); 257 static DmtxBoolean IsCTX(int scheme); 258 static void ShiftValueListBy3(DmtxByteList *list, DmtxPassFail *passFail); 259 260 /* dmtxencodeedifact.c */ 261 static void EncodeNextChunkEdifact(DmtxEncodeStream *stream); 262 static void AppendValueEdifact(DmtxEncodeStream *stream, DmtxByte value); 263 static void CompleteIfDoneEdifact(DmtxEncodeStream *stream, int sizeIdxRequest); 264 265 /* dmtxencodebase256.c */ 266 static void EncodeNextChunkBase256(DmtxEncodeStream *stream); 267 static void AppendValueBase256(DmtxEncodeStream *stream, DmtxByte value); 268 static void CompleteIfDoneBase256(DmtxEncodeStream *stream, int sizeIdxRequest); 269 static void UpdateBase256ChainHeader(DmtxEncodeStream *stream, int perfectSizeIdx); 270 static void Base256OutputChainInsertFirst(DmtxEncodeStream *stream); 271 static void Base256OutputChainRemoveFirst(DmtxEncodeStream *stream); 272 static DmtxByte Randomize255State(DmtxByte cwValue, int cwPosition); 273 static unsigned char UnRandomize255State(unsigned char value, int idx); 274 275 static const int dmtxNeighborNone = 8; 276 static const int dmtxPatternX[] = { -1, 0, 1, 1, 1, 0, -1, -1 }; 277 static const int dmtxPatternY[] = { -1, -1, -1, 0, 1, 1, 1, 0 }; 278 static const DmtxPointFlow dmtxBlankEdge = { 0, 0, 0, DmtxUndefined, { -1, -1 } }; 279 280 /*@ +charint @*/ 281 282 static int rHvX[] = 283 { 256, 256, 256, 256, 255, 255, 255, 254, 254, 253, 252, 251, 250, 249, 248, 284 247, 246, 245, 243, 242, 241, 239, 237, 236, 234, 232, 230, 228, 226, 224, 285 222, 219, 217, 215, 212, 210, 207, 204, 202, 199, 196, 193, 190, 187, 184, 286 181, 178, 175, 171, 168, 165, 161, 158, 154, 150, 147, 143, 139, 136, 132, 287 128, 124, 120, 116, 112, 108, 104, 100, 96, 92, 88, 83, 79, 75, 71, 288 66, 62, 58, 53, 49, 44, 40, 36, 31, 27, 22, 18, 13, 9, 4, 289 0, -4, -9, -13, -18, -22, -27, -31, -36, -40, -44, -49, -53, -58, -62, 290 -66, -71, -75, -79, -83, -88, -92, -96, -100, -104, -108, -112, -116, -120, -124, 291 -128, -132, -136, -139, -143, -147, -150, -154, -158, -161, -165, -168, -171, -175, -178, 292 -181, -184, -187, -190, -193, -196, -199, -202, -204, -207, -210, -212, -215, -217, -219, 293 -222, -224, -226, -228, -230, -232, -234, -236, -237, -239, -241, -242, -243, -245, -246, 294 -247, -248, -249, -250, -251, -252, -253, -254, -254, -255, -255, -255, -256, -256, -256 }; 295 296 static int rHvY[] = 297 { 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 44, 49, 53, 58, 62, 298 66, 71, 75, 79, 83, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124, 299 128, 132, 136, 139, 143, 147, 150, 154, 158, 161, 165, 168, 171, 175, 178, 300 181, 184, 187, 190, 193, 196, 199, 202, 204, 207, 210, 212, 215, 217, 219, 301 222, 224, 226, 228, 230, 232, 234, 236, 237, 239, 241, 242, 243, 245, 246, 302 247, 248, 249, 250, 251, 252, 253, 254, 254, 255, 255, 255, 256, 256, 256, 303 256, 256, 256, 256, 255, 255, 255, 254, 254, 253, 252, 251, 250, 249, 248, 304 247, 246, 245, 243, 242, 241, 239, 237, 236, 234, 232, 230, 228, 226, 224, 305 222, 219, 217, 215, 212, 210, 207, 204, 202, 199, 196, 193, 190, 187, 184, 306 181, 178, 175, 171, 168, 165, 161, 158, 154, 150, 147, 143, 139, 136, 132, 307 128, 124, 120, 116, 112, 108, 104, 100, 96, 92, 88, 83, 79, 75, 71, 308 66, 62, 58, 53, 49, 44, 40, 36, 31, 27, 22, 18, 13, 9, 4 }; 309 310 /*@ -charint @*/ 311 312 enum DmtxErrorMessage { 313 DmtxErrorUnknown, 314 DmtxErrorUnsupportedCharacter, 315 DmtxErrorNotOnByteBoundary, 316 DmtxErrorIllegalParameterValue, 317 DmtxErrorEmptyList, 318 DmtxErrorOutOfBounds, 319 DmtxErrorMessageTooLarge, 320 DmtxErrorCantCompactNonDigits, 321 DmtxErrorUnexpectedScheme, 322 DmtxErrorIncompleteValueList 323 }; 324 325 static char *dmtxErrorMessage[] = { 326 "Unknown error", 327 "Unsupported character", 328 "Not on byte boundary", 329 "Illegal parameter value", 330 "Encountered empty list", 331 "Out of bounds", 332 "Message too large", 333 "Can't compact non-digits", 334 "Encountered unexpected scheme", 335 "Encountered incomplete value list" 336 }; 337 338 #endif 339