1 // © 2016 and later: Unicode, Inc. and others. 2 // License & terms of use: http://www.unicode.org/copyright.html 3 /* 4 ****************************************************************************** 5 * 6 * Copyright (C) 1999-2016, International Business Machines 7 * Corporation and others. All Rights Reserved. 8 * 9 ****************************************************************************** 10 * file name: ubidiimp.h 11 * encoding: UTF-8 12 * tab size: 8 (not used) 13 * indentation:4 14 * 15 * created on: 1999aug06 16 * created by: Markus W. Scherer, updated by Matitiahu Allouche 17 */ 18 19 #ifndef UBIDIIMP_H 20 #define UBIDIIMP_H 21 22 #include "unicode/utypes.h" 23 #include "unicode/ubidi.h" 24 #include "unicode/uchar.h" 25 #include "ubidi_props.h" 26 27 /* miscellaneous definitions ---------------------------------------------- */ 28 29 typedef uint8_t DirProp; 30 typedef uint32_t Flags; 31 32 /* Comparing the description of the BiDi algorithm with this implementation 33 is easier with the same names for the BiDi types in the code as there. 34 See UCharDirection in uchar.h . 35 */ 36 enum { 37 L= U_LEFT_TO_RIGHT, /* 0 */ 38 R= U_RIGHT_TO_LEFT, /* 1 */ 39 EN= U_EUROPEAN_NUMBER, /* 2 */ 40 ES= U_EUROPEAN_NUMBER_SEPARATOR, /* 3 */ 41 ET= U_EUROPEAN_NUMBER_TERMINATOR, /* 4 */ 42 AN= U_ARABIC_NUMBER, /* 5 */ 43 CS= U_COMMON_NUMBER_SEPARATOR, /* 6 */ 44 B= U_BLOCK_SEPARATOR, /* 7 */ 45 S= U_SEGMENT_SEPARATOR, /* 8 */ 46 WS= U_WHITE_SPACE_NEUTRAL, /* 9 */ 47 ON= U_OTHER_NEUTRAL, /* 10 */ 48 LRE=U_LEFT_TO_RIGHT_EMBEDDING, /* 11 */ 49 LRO=U_LEFT_TO_RIGHT_OVERRIDE, /* 12 */ 50 AL= U_RIGHT_TO_LEFT_ARABIC, /* 13 */ 51 RLE=U_RIGHT_TO_LEFT_EMBEDDING, /* 14 */ 52 RLO=U_RIGHT_TO_LEFT_OVERRIDE, /* 15 */ 53 PDF=U_POP_DIRECTIONAL_FORMAT, /* 16 */ 54 NSM=U_DIR_NON_SPACING_MARK, /* 17 */ 55 BN= U_BOUNDARY_NEUTRAL, /* 18 */ 56 FSI=U_FIRST_STRONG_ISOLATE, /* 19 */ 57 LRI=U_LEFT_TO_RIGHT_ISOLATE, /* 20 */ 58 RLI=U_RIGHT_TO_LEFT_ISOLATE, /* 21 */ 59 PDI=U_POP_DIRECTIONAL_ISOLATE, /* 22 */ 60 ENL, /* EN after W7 */ /* 23 */ 61 ENR, /* EN not subject to W7 */ /* 24 */ 62 dirPropCount 63 }; 64 65 /* Sometimes, bit values are more appropriate 66 to deal with directionality properties. 67 Abbreviations in these macro names refer to names 68 used in the BiDi algorithm. 69 */ 70 #define DIRPROP_FLAG(dir) (1UL<<(dir)) 71 #define PURE_DIRPROP(prop) ((prop)&~0xE0) ????????????????????????? 72 73 /* special flag for multiple runs from explicit embedding codes */ 74 #define DIRPROP_FLAG_MULTI_RUNS (1UL<<31) 75 76 /* are there any characters that are LTR or RTL? */ 77 #define MASK_LTR (DIRPROP_FLAG(L)|DIRPROP_FLAG(EN)|DIRPROP_FLAG(ENL)|DIRPROP_FLAG(ENR)|DIRPROP_FLAG(AN)|DIRPROP_FLAG(LRE)|DIRPROP_FLAG(LRO)|DIRPROP_FLAG(LRI)) 78 #define MASK_RTL (DIRPROP_FLAG(R)|DIRPROP_FLAG(AL)|DIRPROP_FLAG(RLE)|DIRPROP_FLAG(RLO)|DIRPROP_FLAG(RLI)) 79 #define MASK_R_AL (DIRPROP_FLAG(R)|DIRPROP_FLAG(AL)) 80 #define MASK_STRONG_EN_AN (DIRPROP_FLAG(L)|DIRPROP_FLAG(R)|DIRPROP_FLAG(AL)|DIRPROP_FLAG(EN)|DIRPROP_FLAG(AN)) 81 82 /* explicit embedding codes */ 83 #define MASK_EXPLICIT (DIRPROP_FLAG(LRE)|DIRPROP_FLAG(LRO)|DIRPROP_FLAG(RLE)|DIRPROP_FLAG(RLO)|DIRPROP_FLAG(PDF)) 84 85 /* explicit isolate codes */ 86 #define MASK_ISO (DIRPROP_FLAG(LRI)|DIRPROP_FLAG(RLI)|DIRPROP_FLAG(FSI)|DIRPROP_FLAG(PDI)) 87 88 #define MASK_BN_EXPLICIT (DIRPROP_FLAG(BN)|MASK_EXPLICIT) 89 90 /* paragraph and segment separators */ 91 #define MASK_B_S (DIRPROP_FLAG(B)|DIRPROP_FLAG(S)) 92 93 /* all types that are counted as White Space or Neutral in some steps */ 94 #define MASK_WS (MASK_B_S|DIRPROP_FLAG(WS)|MASK_BN_EXPLICIT|MASK_ISO) 95 96 /* types that are neutrals or could becomes neutrals in (Wn) */ 97 #define MASK_POSSIBLE_N (DIRPROP_FLAG(ON)|DIRPROP_FLAG(CS)|DIRPROP_FLAG(ES)|DIRPROP_FLAG(ET)|MASK_WS) 98 99 /* 100 * These types may be changed to "e", 101 * the embedding type (L or R) of the run, 102 * in the BiDi algorithm (N2) 103 */ 104 #define MASK_EMBEDDING (DIRPROP_FLAG(NSM)|MASK_POSSIBLE_N) 105 106 /* the dirProp's L and R are defined to 0 and 1 values in UCharDirection */ 107 #define GET_LR_FROM_LEVEL(level) ((DirProp)((level)&1)) 108 109 #define IS_DEFAULT_LEVEL(level) ((level)>=0xfe) 110 111 /* 112 * The following bit is used for the directional isolate status. 113 * Stack entries corresponding to isolate sequences are greater than ISOLATE. 114 */ 115 #define ISOLATE 0x0100 116 117 U_CFUNC UBiDiLevel 118 ubidi_getParaLevelAtIndex(const UBiDi *pBiDi, int32_t index); 119 120 #define GET_PARALEVEL(ubidi, index) \ 121 ((UBiDiLevel)(!(ubidi)->defaultParaLevel || (index)<(ubidi)->paras[0].limit ? \ 122 (ubidi)->paraLevel : ubidi_getParaLevelAtIndex((ubidi), (index)))) 123 124 /* number of paras entries allocated initially without malloc */ 125 #define SIMPLE_PARAS_COUNT 10 126 /* number of isolate entries allocated initially without malloc */ 127 #define SIMPLE_ISOLATES_COUNT 5 128 /* number of isolate run entries for paired brackets allocated initially without malloc */ 129 #define SIMPLE_OPENINGS_COUNT 20 130 131 #define CR 0x000D 132 #define LF 0x000A 133 134 /* Run structure for reordering --------------------------------------------- */ 135 enum { 136 LRM_BEFORE=1, 137 LRM_AFTER=2, 138 RLM_BEFORE=4, 139 RLM_AFTER=8 140 }; 141 142 typedef struct Para { 143 int32_t limit; 144 int32_t level; 145 } Para; 146 147 enum { /* flags for Opening.flags */ 148 FOUND_L=DIRPROP_FLAG(L), 149 FOUND_R=DIRPROP_FLAG(R) 150 }; 151 152 typedef struct Opening { 153 int32_t position; /* position of opening bracket */ 154 int32_t match; /* matching char or -position of closing bracket */ 155 int32_t contextPos; /* position of last strong char found before opening */ 156 uint16_t flags; /* bits for L or R/AL found within the pair */ 157 UBiDiDirection contextDir; /* L or R according to last strong char before opening */ 158 uint8_t filler; /* to complete a nice multiple of 4 chars */ 159 } Opening; 160 161 typedef struct IsoRun { 162 int32_t contextPos; /* position of char determining context */ 163 uint16_t start; /* index of first opening entry for this run */ 164 uint16_t limit; /* index after last opening entry for this run */ 165 UBiDiLevel level; /* level of this run */ 166 DirProp lastStrong; /* bidi class of last strong char found in this run */ 167 DirProp lastBase; /* bidi class of last base char found in this run */ 168 UBiDiDirection contextDir; /* L or R to use as context for following openings */ 169 } IsoRun; 170 171 typedef struct BracketData { 172 UBiDi *pBiDi; 173 /* array of opening entries which should be enough in most cases; no malloc() */ 174 Opening simpleOpenings[SIMPLE_OPENINGS_COUNT]; 175 Opening *openings; /* pointer to current array of entries */ 176 int32_t openingsCount; /* number of allocated entries */ 177 int32_t isoRunLast; /* index of last used entry */ 178 /* array of nested isolated sequence entries; can never excess UBIDI_MAX_EXPLICIT_LEVEL 179 + 1 for index 0, + 1 for before the first isolated sequence */ 180 IsoRun isoRuns[UBIDI_MAX_EXPLICIT_LEVEL+2]; 181 UBool isNumbersSpecial; /* reordering mode for NUMBERS_SPECIAL */ 182 } BracketData; 183 184 typedef struct Isolate { 185 int32_t startON; 186 int32_t start1; 187 int32_t state; 188 int16_t stateImp; 189 } Isolate; 190 191 typedef struct Run { 192 int32_t logicalStart, /* first character of the run; b31 indicates even/odd level */ 193 visualLimit, /* last visual position of the run +1 */ 194 insertRemove; /* if >0, flags for inserting LRM/RLM before/after run, 195 if <0, count of bidi controls within run */ 196 } Run; 197 198 /* in a Run, logicalStart will get this bit set if the run level is odd */ 199 #define INDEX_ODD_BIT (1UL<<31) 200 201 #define MAKE_INDEX_ODD_PAIR(index, level) ((index)|((int32_t)(level)<<31)) 202 #define ADD_ODD_BIT_FROM_LEVEL(x, level) ((x)|=((int32_t)(level)<<31)) 203 #define REMOVE_ODD_BIT(x) ((x)&=~INDEX_ODD_BIT) 204 205 #define GET_INDEX(x) ((x)&~INDEX_ODD_BIT) 206 #define GET_ODD_BIT(x) ((uint32_t)(x)>>31) 207 #define IS_ODD_RUN(x) ((UBool)(((x)&INDEX_ODD_BIT)!=0)) 208 #define IS_EVEN_RUN(x) ((UBool)(((x)&INDEX_ODD_BIT)==0)) 209 210 U_CFUNC UBool 211 ubidi_getRuns(UBiDi *pBiDi, UErrorCode *pErrorCode); 212 213 /** BiDi control code points */ 214 enum { 215 ZWNJ_CHAR=0x200c, 216 ZWJ_CHAR, 217 LRM_CHAR, 218 RLM_CHAR, 219 LRE_CHAR=0x202a, 220 RLE_CHAR, 221 PDF_CHAR, 222 LRO_CHAR, 223 RLO_CHAR, 224 LRI_CHAR=0x2066, 225 RLI_CHAR, 226 FSI_CHAR, 227 PDI_CHAR 228 }; 229 230 #define IS_BIDI_CONTROL_CHAR(c) (((uint32_t)(c)&0xfffffffc)==ZWNJ_CHAR || (uint32_t)((c)-LRE_CHAR)<5 || (uint32_t)((c)-LRI_CHAR)<4) 231 232 /* InsertPoints structure for noting where to put BiDi marks ---------------- */ 233 234 typedef struct Point { 235 int32_t pos; /* position in text */ 236 int32_t flag; /* flag for LRM/RLM, before/after */ 237 } Point; 238 239 typedef struct InsertPoints { 240 int32_t capacity; /* number of points allocated */ 241 int32_t size; /* number of points used */ 242 int32_t confirmed; /* number of points confirmed */ 243 UErrorCode errorCode; /* for eventual memory shortage */ 244 Point *points; /* pointer to array of points */ 245 } InsertPoints; 246 247 248 /* UBiDi structure ----------------------------------------------------------- */ 249 250 struct UBiDi { 251 /* pointer to parent paragraph object (pointer to self if this object is 252 * a paragraph object); set to NULL in a newly opened object; set to a 253 * real value after a successful execution of ubidi_setPara or ubidi_setLine 254 */ 255 const UBiDi * pParaBiDi; 256 257 /* alias pointer to the current text */ 258 const UChar *text; 259 260 /* length of the current text */ 261 int32_t originalLength; 262 263 /* if the UBIDI_OPTION_STREAMING option is set, this is the length 264 * of text actually processed by ubidi_setPara, which may be shorter than 265 * the original length. 266 * Otherwise, it is identical to the original length. 267 */ 268 int32_t length; 269 270 /* if the UBIDI_OPTION_REMOVE_CONTROLS option is set, and/or 271 * marks are allowed to be inserted in one of the reordering mode, the 272 * length of the result string may be different from the processed length. 273 */ 274 int32_t resultLength; 275 276 /* memory sizes in bytes */ 277 int32_t dirPropsSize, levelsSize, openingsSize, parasSize, runsSize, isolatesSize; 278 279 /* allocated memory */ 280 DirProp *dirPropsMemory; 281 UBiDiLevel *levelsMemory; 282 Opening *openingsMemory; 283 Para *parasMemory; 284 Run *runsMemory; 285 Isolate *isolatesMemory; 286 287 /* indicators for whether memory may be allocated after ubidi_open() */ 288 UBool mayAllocateText, mayAllocateRuns; 289 290 /* arrays with one value per text-character */ 291 DirProp *dirProps; 292 UBiDiLevel *levels; 293 294 /* are we performing an approximation of the "inverse BiDi" algorithm? */ 295 UBool isInverse; 296 297 /* are we using the basic algorithm or its variation? */ 298 UBiDiReorderingMode reorderingMode; 299 300 /* UBIDI_REORDER_xxx values must be ordered so that all the regular 301 * logical to visual modes come first, and all inverse BiDi modes 302 * come last. 303 */ 304 #define UBIDI_REORDER_LAST_LOGICAL_TO_VISUAL UBIDI_REORDER_NUMBERS_SPECIAL 305 306 /* bitmask for reordering options */ 307 uint32_t reorderingOptions; 308 309 /* must block separators receive level 0? */ 310 UBool orderParagraphsLTR; 311 312 /* the paragraph level */ 313 UBiDiLevel paraLevel; 314 /* original paraLevel when contextual */ 315 /* must be one of UBIDI_DEFAULT_xxx or 0 if not contextual */ 316 UBiDiLevel defaultParaLevel; 317 318 /* context data */ 319 const UChar *prologue; 320 int32_t proLength; 321 const UChar *epilogue; 322 int32_t epiLength; 323 324 /* the following is set in ubidi_setPara, used in processPropertySeq */ 325 const struct ImpTabPair * pImpTabPair; /* pointer to levels state table pair */ 326 327 /* the overall paragraph or line directionality - see UBiDiDirection */ 328 UBiDiDirection direction; 329 330 /* flags is a bit set for which directional properties are in the text */ 331 Flags flags; 332 333 /* lastArabicPos is index to the last AL in the text, -1 if none */ 334 int32_t lastArabicPos; 335 336 /* characters after trailingWSStart are WS and are */ 337 /* implicitly at the paraLevel (rule (L1)) - levels may not reflect that */ 338 int32_t trailingWSStart; 339 340 /* fields for paragraph handling */ 341 int32_t paraCount; /* set in getDirProps() */ 342 /* filled in getDirProps() */ 343 Para *paras; 344 345 /* for relatively short text, we only need a tiny array of paras (no malloc()) */ 346 Para simpleParas[SIMPLE_PARAS_COUNT]; 347 348 /* fields for line reordering */ 349 int32_t runCount; /* ==-1: runs not set up yet */ 350 Run *runs; 351 352 /* for non-mixed text, we only need a tiny array of runs (no malloc()) */ 353 Run simpleRuns[1]; 354 355 /* maximum or current nesting depth of isolate sequences */ 356 /* Within resolveExplicitLevels() and checkExplicitLevels(), this is the maximal 357 nesting encountered. 358 Within resolveImplicitLevels(), this is the index of the current isolates 359 stack entry. */ 360 int32_t isolateCount; 361 Isolate *isolates; 362 363 /* for simple text, have a small stack (no malloc()) */ 364 Isolate simpleIsolates[SIMPLE_ISOLATES_COUNT]; 365 366 /* for inverse Bidi with insertion of directional marks */ 367 InsertPoints insertPoints; 368 369 /* for option UBIDI_OPTION_REMOVE_CONTROLS */ 370 int32_t controlCount; 371 372 /* for Bidi class callback */ 373 UBiDiClassCallback *fnClassCallback; /* action pointer */ 374 const void *coClassCallback; /* context pointer */ 375 }; 376 377 #define IS_VALID_PARA(x) ((x) && ((x)->pParaBiDi==(x))) 378 #define IS_VALID_PARA_OR_LINE(x) ((x) && ((x)->pParaBiDi==(x) || (((x)->pParaBiDi) && (x)->pParaBiDi->pParaBiDi==(x)->pParaBiDi))) 379 380 typedef union { 381 DirProp *dirPropsMemory; 382 UBiDiLevel *levelsMemory; 383 Opening *openingsMemory; 384 Para *parasMemory; 385 Run *runsMemory; 386 Isolate *isolatesMemory; 387 } BidiMemoryForAllocation; 388 389 /* Macros for initial checks at function entry */ 390 #define RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrcode, retvalue) \ 391 if((pErrcode)==NULL || U_FAILURE(*pErrcode)) return retvalue 392 #define RETURN_IF_NOT_VALID_PARA(bidi, errcode, retvalue) \ 393 if(!IS_VALID_PARA(bidi)) { \ 394 errcode=U_INVALID_STATE_ERROR; \ 395 return retvalue; \ 396 } 397 #define RETURN_IF_NOT_VALID_PARA_OR_LINE(bidi, errcode, retvalue) \ 398 if(!IS_VALID_PARA_OR_LINE(bidi)) { \ 399 errcode=U_INVALID_STATE_ERROR; \ 400 return retvalue; \ 401 } 402 #define RETURN_IF_BAD_RANGE(arg, start, limit, errcode, retvalue) \ 403 if((arg)<(start) || (arg)>=(limit)) { \ 404 (errcode)=U_ILLEGAL_ARGUMENT_ERROR; \ 405 return retvalue; \ 406 } 407 408 #define RETURN_VOID_IF_NULL_OR_FAILING_ERRCODE(pErrcode) \ 409 if((pErrcode)==NULL || U_FAILURE(*pErrcode)) return 410 #define RETURN_VOID_IF_NOT_VALID_PARA(bidi, errcode) \ 411 if(!IS_VALID_PARA(bidi)) { \ 412 errcode=U_INVALID_STATE_ERROR; \ 413 return; \ 414 } 415 #define RETURN_VOID_IF_NOT_VALID_PARA_OR_LINE(bidi, errcode) \ 416 if(!IS_VALID_PARA_OR_LINE(bidi)) { \ 417 errcode=U_INVALID_STATE_ERROR; \ 418 return; \ 419 } 420 #define RETURN_VOID_IF_BAD_RANGE(arg, start, limit, errcode) \ 421 if((arg)<(start) || (arg)>=(limit)) { \ 422 (errcode)=U_ILLEGAL_ARGUMENT_ERROR; \ 423 return; \ 424 } 425 426 /* helper function to (re)allocate memory if allowed */ 427 U_CFUNC UBool 428 ubidi_getMemory(BidiMemoryForAllocation *pMemory, int32_t *pSize, UBool mayAllocate, int32_t sizeNeeded); 429 430 /* helper macros for each allocated array in UBiDi */ 431 #define getDirPropsMemory(pBiDi, length) \ 432 ubidi_getMemory((BidiMemoryForAllocation *)&(pBiDi)->dirPropsMemory, &(pBiDi)->dirPropsSize, \ 433 (pBiDi)->mayAllocateText, (length)) 434 435 #define getLevelsMemory(pBiDi, length) \ 436 ubidi_getMemory((BidiMemoryForAllocation *)&(pBiDi)->levelsMemory, &(pBiDi)->levelsSize, \ 437 (pBiDi)->mayAllocateText, (length)) 438 439 #define getRunsMemory(pBiDi, length) \ 440 ubidi_getMemory((BidiMemoryForAllocation *)&(pBiDi)->runsMemory, &(pBiDi)->runsSize, \ 441 (pBiDi)->mayAllocateRuns, (length)*sizeof(Run)) 442 443 /* additional macros used by ubidi_open() - always allow allocation */ 444 #define getInitialDirPropsMemory(pBiDi, length) \ 445 ubidi_getMemory((BidiMemoryForAllocation *)&(pBiDi)->dirPropsMemory, &(pBiDi)->dirPropsSize, \ 446 TRUE, (length)) 447 448 #define getInitialLevelsMemory(pBiDi, length) \ 449 ubidi_getMemory((BidiMemoryForAllocation *)&(pBiDi)->levelsMemory, &(pBiDi)->levelsSize, \ 450 TRUE, (length)) 451 452 #define getInitialOpeningsMemory(pBiDi, length) \ 453 ubidi_getMemory((BidiMemoryForAllocation *)&(pBiDi)->openingsMemory, &(pBiDi)->openingsSize, \ 454 TRUE, (length)*sizeof(Opening)) 455 456 #define getInitialParasMemory(pBiDi, length) \ 457 ubidi_getMemory((BidiMemoryForAllocation *)&(pBiDi)->parasMemory, &(pBiDi)->parasSize, \ 458 TRUE, (length)*sizeof(Para)) 459 460 #define getInitialRunsMemory(pBiDi, length) \ 461 ubidi_getMemory((BidiMemoryForAllocation *)&(pBiDi)->runsMemory, &(pBiDi)->runsSize, \ 462 TRUE, (length)*sizeof(Run)) 463 464 #define getInitialIsolatesMemory(pBiDi, length) \ 465 ubidi_getMemory((BidiMemoryForAllocation *)&(pBiDi)->isolatesMemory, &(pBiDi)->isolatesSize, \ 466 TRUE, (length)*sizeof(Isolate)) 467 468 #endif 469