triehash/tests/test-multi-byte-level

   1 #!/bin/sh
   2 . $(dirname $(readlink -f $0))/framework.sh
   3
   4 # Check that building a single-byte trie works
   5 testsuccessequal "\
   6 ┌────────────────────────────────────────────────────┐
   7 │                   Initial trie                     │
   8 └────────────────────────────────────────────────────┘
   9
  10 ├── V
  11 │   ├── e
  12 │   │   ├── r
  13 │   │   │   ├── y
  14 │   │   │   │   ├── L
  15 │   │   │   │   │   ├── o
  16 │   │   │   │   │   │   ├── n
  17 │   │   │   │   │   │   │   ├── g
  18 │   │   │   │   │   │   │   │   ├── W
  19 │   │   │   │   │   │   │   │   │   ├── o
  20 │   │   │   │   │   │   │   │   │   │   ├── r
  21 │   │   │   │   │   │   │   │   │   │   │   ├── d → VeryLongWord
  22 ├── W
  23 │   ├── o
  24 │   │   ├── r
  25 │   │   │   ├── d → Word
  26 │   │   │   │   ├── -
  27 │   │   │   │   │   ├── _
  28 │   │   │   │   │   │   ├── 0 → Word-_0
  29 │   │   │   │   ├── 2 → Label
  30 ┌────────────────────────────────────────────────────┐
  31 │                   Rebuilt trie                     │
  32 └────────────────────────────────────────────────────┘
  33
  34 ├── V
  35 │   ├── e
  36 │   │   ├── r
  37 │   │   │   ├── y
  38 │   │   │   │   ├── L
  39 │   │   │   │   │   ├── o
  40 │   │   │   │   │   │   ├── n
  41 │   │   │   │   │   │   │   ├── g
  42 │   │   │   │   │   │   │   │   ├── W
  43 │   │   │   │   │   │   │   │   │   ├── o
  44 │   │   │   │   │   │   │   │   │   │   ├── r
  45 │   │   │   │   │   │   │   │   │   │   │   ├── d → VeryLongWord
  46 ├── W
  47 │   ├── o
  48 │   │   ├── r
  49 │   │   │   ├── d → Word
  50 │   │   │   │   ├── -
  51 │   │   │   │   │   ├── _
  52 │   │   │   │   │   │   ├── 0 → Word-_0
  53 │   │   │   │   ├── 2 → Label
  54 ┌────────────────────────────────────────────────────┐
  55 │              Trie for words of length 4            │
  56 └────────────────────────────────────────────────────┘
  57
  58 ├── W
  59 │   ├── o
  60 │   │   ├── r
  61 │   │   │   ├── d → Word
  62 ┌────────────────────────────────────────────────────┐
  63 │              Trie for words of length 5            │
  64 └────────────────────────────────────────────────────┘
  65
  66 ├── W
  67 │   ├── o
  68 │   │   ├── r
  69 │   │   │   ├── d
  70 │   │   │   │   ├── 2 → Label
  71 ┌────────────────────────────────────────────────────┐
  72 │              Trie for words of length 7            │
  73 └────────────────────────────────────────────────────┘
  74
  75 ├── W
  76 │   ├── o
  77 │   │   ├── r
  78 │   │   │   ├── d
  79 │   │   │   │   ├── -
  80 │   │   │   │   │   ├── _
  81 │   │   │   │   │   │   ├── 0 → Word-_0
  82 ┌────────────────────────────────────────────────────┐
  83 │              Trie for words of length 12           │
  84 └────────────────────────────────────────────────────┘
  85
  86 ├── V
  87 │   ├── e
  88 │   │   ├── r
  89 │   │   │   ├── y
  90 │   │   │   │   ├── L
  91 │   │   │   │   │   ├── o
  92 │   │   │   │   │   │   ├── n
  93 │   │   │   │   │   │   │   ├── g
  94 │   │   │   │   │   │   │   │   ├── W
  95 │   │   │   │   │   │   │   │   │   ├── o
  96 │   │   │   │   │   │   │   │   │   │   ├── r
  97 │   │   │   │   │   │   │   │   │   │   │   ├── d → VeryLongWord" triehash --multi-byte=0 -l tree /dev/stdin
  98
  99 # Two byte optimization
 100 testsuccessequal "\
 101 ┌────────────────────────────────────────────────────┐
 102 │                   Initial trie                     │
 103 └────────────────────────────────────────────────────┘
 104
 105 ├── Ve
 106 │   ├── ry
 107 │   │   ├── Lo
 108 │   │   │   ├── ng
 109 │   │   │   │   ├── Wo
 110 │   │   │   │   │   ├── rd → VeryLongWord
 111 ├── Wo
 112 │   ├── rd → Word
 113 │   │   ├── -_
 114 │   │   │   ├── 0 → Word-_0
 115 │   │   ├── 2 → Label
 116 ┌────────────────────────────────────────────────────┐
 117 │                   Rebuilt trie                     │
 118 └────────────────────────────────────────────────────┘
 119
 120 ├── Ve
 121 │   ├── ry
 122 │   │   ├── Lo
 123 │   │   │   ├── ng
 124 │   │   │   │   ├── Wo
 125 │   │   │   │   │   ├── rd → VeryLongWord
 126 ├── Wo
 127 │   ├── rd → Word
 128 │   │   ├── -
 129 │   │   │   ├── _0 → Word-_0
 130 │   │   ├── 2 → Label
 131 ┌────────────────────────────────────────────────────┐
 132 │              Trie for words of length 4            │
 133 └────────────────────────────────────────────────────┘
 134
 135 ├── Wo
 136 │   ├── rd → Word
 137 ┌────────────────────────────────────────────────────┐
 138 │              Trie for words of length 5            │
 139 └────────────────────────────────────────────────────┘
 140
 141 ├── Wo
 142 │   ├── rd
 143 │   │   ├── 2 → Label
 144 ┌────────────────────────────────────────────────────┐
 145 │              Trie for words of length 7            │
 146 └────────────────────────────────────────────────────┘
 147
 148 ├── Wo
 149 │   ├── rd
 150 │   │   ├── -_
 151 │   │   │   ├── 0 → Word-_0
 152 ┌────────────────────────────────────────────────────┐
 153 │              Trie for words of length 12           │
 154 └────────────────────────────────────────────────────┘
 155
 156 ├── Ve
 157 │   ├── ry
 158 │   │   ├── Lo
 159 │   │   │   ├── ng
 160 │   │   │   │   ├── Wo
 161 │   │   │   │   │   ├── rd → VeryLongWord" triehash --multi-byte=1 -l tree /dev/stdin
 162 # Four byte optimization
 163 testsuccessequal "\
 164 ┌────────────────────────────────────────────────────┐
 165 │                   Initial trie                     │
 166 └────────────────────────────────────────────────────┘
 167
 168 ├── Very
 169 │   ├── Long
 170 │   │   ├── Word → VeryLongWord
 171 ├── Word → Word
 172 │   ├── -
 173 │   │   ├── _
 174 │   │   │   ├── 0 → Word-_0
 175 │   ├── 2 → Label
 176 ┌────────────────────────────────────────────────────┐
 177 │                   Rebuilt trie                     │
 178 └────────────────────────────────────────────────────┘
 179
 180 ├── Very
 181 │   ├── Long
 182 │   │   ├── Word → VeryLongWord
 183 ├── Word → Word
 184 │   ├── -
 185 │   │   ├── _
 186 │   │   │   ├── 0 → Word-_0
 187 │   ├── 2 → Label
 188 ┌────────────────────────────────────────────────────┐
 189 │              Trie for words of length 4            │
 190 └────────────────────────────────────────────────────┘
 191
 192 ├── Word → Word
 193 ┌────────────────────────────────────────────────────┐
 194 │              Trie for words of length 5            │
 195 └────────────────────────────────────────────────────┘
 196
 197 ├── Word
 198 │   ├── 2 → Label
 199 ┌────────────────────────────────────────────────────┐
 200 │              Trie for words of length 7            │
 201 └────────────────────────────────────────────────────┘
 202
 203 ├── Word
 204 │   ├── -
 205 │   │   ├── _
 206 │   │   │   ├── 0 → Word-_0
 207 ┌────────────────────────────────────────────────────┐
 208 │              Trie for words of length 12           │
 209 └────────────────────────────────────────────────────┘
 210
 211 ├── Very
 212 │   ├── Long
 213 │   │   ├── Word → VeryLongWord" triehash --multi-byte=2 -l tree /dev/stdin
 214 # Eigh byte optimization
 215 testsuccessequal "\
 216 ┌────────────────────────────────────────────────────┐
 217 │                   Initial trie                     │
 218 └────────────────────────────────────────────────────┘
 219
 220 ├── VeryLong
 221 │   ├── W
 222 │   │   ├── o
 223 │   │   │   ├── r
 224 │   │   │   │   ├── d → VeryLongWord
 225 ├── W
 226 │   ├── o
 227 │   │   ├── r
 228 │   │   │   ├── d → Word
 229 │   │   │   │   ├── -
 230 │   │   │   │   │   ├── _
 231 │   │   │   │   │   │   ├── 0 → Word-_0
 232 │   │   │   │   ├── 2 → Label
 233 ┌────────────────────────────────────────────────────┐
 234 │                   Rebuilt trie                     │
 235 └────────────────────────────────────────────────────┘
 236
 237 ├── V
 238 │   ├── eryLongW
 239 │   │   ├── o
 240 │   │   │   ├── r
 241 │   │   │   │   ├── d → VeryLongWord
 242 ├── W
 243 │   ├── o
 244 │   │   ├── r
 245 │   │   │   ├── d → Word
 246 │   │   │   │   ├── -
 247 │   │   │   │   │   ├── _
 248 │   │   │   │   │   │   ├── 0 → Word-_0
 249 │   │   │   │   ├── 2 → Label
 250 ┌────────────────────────────────────────────────────┐
 251 │              Trie for words of length 4            │
 252 └────────────────────────────────────────────────────┘
 253
 254 ├── W
 255 │   ├── o
 256 │   │   ├── r
 257 │   │   │   ├── d → Word
 258 ┌────────────────────────────────────────────────────┐
 259 │              Trie for words of length 5            │
 260 └────────────────────────────────────────────────────┘
 261
 262 ├── W
 263 │   ├── o
 264 │   │   ├── r
 265 │   │   │   ├── d
 266 │   │   │   │   ├── 2 → Label
 267 ┌────────────────────────────────────────────────────┐
 268 │              Trie for words of length 7            │
 269 └────────────────────────────────────────────────────┘
 270
 271 ├── W
 272 │   ├── o
 273 │   │   ├── r
 274 │   │   │   ├── d
 275 │   │   │   │   ├── -
 276 │   │   │   │   │   ├── _
 277 │   │   │   │   │   │   ├── 0 → Word-_0
 278 ┌────────────────────────────────────────────────────┐
 279 │              Trie for words of length 12           │
 280 └────────────────────────────────────────────────────┘
 281
 282 ├── VeryLong
 283 │   ├── W
 284 │   │   ├── o
 285 │   │   │   ├── r
 286 │   │   │   │   ├── d → VeryLongWord" triehash --multi-byte=3 -l tree /dev/stdin
 287
 288
 289 # Check that building a multi-byte trie works
 290 testsuccessequal "\
 291 ┌────────────────────────────────────────────────────┐
 292 │                   Initial trie                     │
 293 └────────────────────────────────────────────────────┘
 294
 295 ├── VeryLong
 296 │   ├── Word → VeryLongWord
 297 ├── Word → Word
 298 │   ├── -
 299 │   │   ├── _
 300 │   │   │   ├── 0 → Word-_0
 301 │   ├── 2 → Label
 302 ┌────────────────────────────────────────────────────┐
 303 │                   Rebuilt trie                     │
 304 └────────────────────────────────────────────────────┘
 305
 306 ├── Very
 307 │   ├── LongWord → VeryLongWord
 308 ├── Word → Word
 309 │   ├── -
 310 │   │   ├── _
 311 │   │   │   ├── 0 → Word-_0
 312 │   ├── 2 → Label
 313 ┌────────────────────────────────────────────────────┐
 314 │              Trie for words of length 4            │
 315 └────────────────────────────────────────────────────┘
 316
 317 ├── Word → Word
 318 ┌────────────────────────────────────────────────────┐
 319 │              Trie for words of length 5            │
 320 └────────────────────────────────────────────────────┘
 321
 322 ├── Word
 323 │   ├── 2 → Label
 324 ┌────────────────────────────────────────────────────┐
 325 │              Trie for words of length 7            │
 326 └────────────────────────────────────────────────────┘
 327
 328 ├── Word
 329 │   ├── -
 330 │   │   ├── _
 331 │   │   │   ├── 0 → Word-_0
 332 ┌────────────────────────────────────────────────────┐
 333 │              Trie for words of length 12           │
 334 └────────────────────────────────────────────────────┘
 335
 336 ├── VeryLong
 337 │   ├── Word → VeryLongWord" triehash -l tree /dev/stdin
 338
 339
 340 ###### CHANGE THE WORDS FOR THE FOLLOWING TESTS #######
 341 WORDS="Word"
 342
 343 # Check that we are generating the proper multi-byte and fallback sessions
 344 testsuccessequal "#include \"/dev/null\"
 345 #ifdef __GNUC__
 346 typedef uint16_t __attribute__((aligned (1))) triehash_uu16;
 347 typedef char static_assert16[__alignof__(triehash_uu16) == 1 ? 1 : -1];
 348 typedef uint32_t __attribute__((aligned (1))) triehash_uu32;
 349 typedef char static_assert32[__alignof__(triehash_uu32) == 1 ? 1 : -1];
 350 typedef uint64_t __attribute__((aligned (1))) triehash_uu64;
 351 typedef char static_assert64[__alignof__(triehash_uu64) == 1 ? 1 : -1];
 352 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
 353 #define onechar(c, s, l) (((uint64_t)(c)) << (s))
 354 #else
 355 #define onechar(c, s, l) (((uint64_t)(c)) << (l-8-s))
 356 #endif
 357 #if (!defined(__ARM_ARCH) || defined(__ARM_FEATURE_UNALIGNED)) && !defined(TRIE_HASH_NO_MULTI_BYTE)
 358 #define TRIE_HASH_MULTI_BYTE
 359 #endif
 360 #endif /*GNUC */
 361 #ifdef TRIE_HASH_MULTI_BYTE
 362 static enum PerfectKey PerfectHash4(const char *string)
 363 {
 364     switch(*((triehash_uu32*) &string[0])) {
 365     case 0| onechar('W', 0, 32)| onechar('o', 8, 32)| onechar('r', 16, 32)| onechar('d', 24, 32):
 366         return Word;
 367     }
 368     return Unknown;
 369 }
 370 #else
 371 static enum PerfectKey PerfectHash4(const char *string)
 372 {
 373     switch(string[0]) {
 374     case 'W':
 375         switch(string[1]) {
 376         case 'o':
 377             switch(string[2]) {
 378             case 'r':
 379                 switch(string[3]) {
 380                 case 'd':
 381                     return Word;
 382                 }
 383             }
 384         }
 385     }
 386     return Unknown;
 387 }
 388 #endif /* TRIE_HASH_MULTI_BYTE */
 389  enum PerfectKey PerfectHash(const char *string, size_t length)
 390 {
 391     switch (length) {
 392     case 4:
 393         return PerfectHash4(string);
 394     default:
 395         return Unknown;
 396     }
 397 }" triehash -H /dev/null /dev/stdin
 398
 399
 400 # Check that we are generating no multi-byte session
 401 testsuccessequal "#include \"/dev/null\"
 402 static enum PerfectKey PerfectHash4(const char *string)
 403 {
 404     switch(string[0]) {
 405     case 'W':
 406         switch(string[1]) {
 407         case 'o':
 408             switch(string[2]) {
 409             case 'r':
 410                 switch(string[3]) {
 411                 case 'd':
 412                     return Word;
 413                 }
 414             }
 415         }
 416     }
 417     return Unknown;
 418 }
 419  enum PerfectKey PerfectHash(const char *string, size_t length)
 420 {
 421     switch (length) {
 422     case 4:
 423         return PerfectHash4(string);
 424     default:
 425         return Unknown;
 426     }
 427 }" triehash --multi-byte=0 -H /dev/null /dev/stdin