Alexandre Lision | 8af73cb | 2013-12-10 14:11:20 -0500 | [diff] [blame] | 1 | /* |
| 2 | * datatypes.c |
| 3 | * |
| 4 | * data types for finite fields and functions for input, output, and |
| 5 | * manipulation |
| 6 | * |
| 7 | * David A. McGrew |
| 8 | * Cisco Systems, Inc. |
| 9 | */ |
| 10 | /* |
| 11 | * |
| 12 | * Copyright (c) 2001-2006 Cisco Systems, Inc. |
| 13 | * All rights reserved. |
| 14 | * |
| 15 | * Redistribution and use in source and binary forms, with or without |
| 16 | * modification, are permitted provided that the following conditions |
| 17 | * are met: |
| 18 | * |
| 19 | * Redistributions of source code must retain the above copyright |
| 20 | * notice, this list of conditions and the following disclaimer. |
| 21 | * |
| 22 | * Redistributions in binary form must reproduce the above |
| 23 | * copyright notice, this list of conditions and the following |
| 24 | * disclaimer in the documentation and/or other materials provided |
| 25 | * with the distribution. |
| 26 | * |
| 27 | * Neither the name of the Cisco Systems, Inc. nor the names of its |
| 28 | * contributors may be used to endorse or promote products derived |
| 29 | * from this software without specific prior written permission. |
| 30 | * |
| 31 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 32 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 33 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS |
| 34 | * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE |
| 35 | * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, |
| 36 | * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
| 37 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR |
| 38 | * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 39 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| 40 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 41 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
| 42 | * OF THE POSSIBILITY OF SUCH DAMAGE. |
| 43 | * |
| 44 | */ |
| 45 | |
| 46 | #include "datatypes.h" |
| 47 | |
| 48 | int |
| 49 | octet_weight[256] = { |
| 50 | 0, 1, 1, 2, 1, 2, 2, 3, |
| 51 | 1, 2, 2, 3, 2, 3, 3, 4, |
| 52 | 1, 2, 2, 3, 2, 3, 3, 4, |
| 53 | 2, 3, 3, 4, 3, 4, 4, 5, |
| 54 | 1, 2, 2, 3, 2, 3, 3, 4, |
| 55 | 2, 3, 3, 4, 3, 4, 4, 5, |
| 56 | 2, 3, 3, 4, 3, 4, 4, 5, |
| 57 | 3, 4, 4, 5, 4, 5, 5, 6, |
| 58 | 1, 2, 2, 3, 2, 3, 3, 4, |
| 59 | 2, 3, 3, 4, 3, 4, 4, 5, |
| 60 | 2, 3, 3, 4, 3, 4, 4, 5, |
| 61 | 3, 4, 4, 5, 4, 5, 5, 6, |
| 62 | 2, 3, 3, 4, 3, 4, 4, 5, |
| 63 | 3, 4, 4, 5, 4, 5, 5, 6, |
| 64 | 3, 4, 4, 5, 4, 5, 5, 6, |
| 65 | 4, 5, 5, 6, 5, 6, 6, 7, |
| 66 | 1, 2, 2, 3, 2, 3, 3, 4, |
| 67 | 2, 3, 3, 4, 3, 4, 4, 5, |
| 68 | 2, 3, 3, 4, 3, 4, 4, 5, |
| 69 | 3, 4, 4, 5, 4, 5, 5, 6, |
| 70 | 2, 3, 3, 4, 3, 4, 4, 5, |
| 71 | 3, 4, 4, 5, 4, 5, 5, 6, |
| 72 | 3, 4, 4, 5, 4, 5, 5, 6, |
| 73 | 4, 5, 5, 6, 5, 6, 6, 7, |
| 74 | 2, 3, 3, 4, 3, 4, 4, 5, |
| 75 | 3, 4, 4, 5, 4, 5, 5, 6, |
| 76 | 3, 4, 4, 5, 4, 5, 5, 6, |
| 77 | 4, 5, 5, 6, 5, 6, 6, 7, |
| 78 | 3, 4, 4, 5, 4, 5, 5, 6, |
| 79 | 4, 5, 5, 6, 5, 6, 6, 7, |
| 80 | 4, 5, 5, 6, 5, 6, 6, 7, |
| 81 | 5, 6, 6, 7, 6, 7, 7, 8 |
| 82 | }; |
| 83 | |
| 84 | int |
| 85 | octet_get_weight(uint8_t octet) { |
| 86 | extern int octet_weight[256]; |
| 87 | |
| 88 | return octet_weight[octet]; |
| 89 | } |
| 90 | |
| 91 | /* |
| 92 | * bit_string is a buffer that is used to hold output strings, e.g. |
| 93 | * for printing. |
| 94 | */ |
| 95 | |
| 96 | /* the value MAX_PRINT_STRING_LEN is defined in datatypes.h */ |
| 97 | |
| 98 | char bit_string[MAX_PRINT_STRING_LEN]; |
| 99 | |
| 100 | uint8_t |
| 101 | nibble_to_hex_char(uint8_t nibble) { |
| 102 | char buf[16] = {'0', '1', '2', '3', '4', '5', '6', '7', |
| 103 | '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' }; |
| 104 | return buf[nibble & 0xF]; |
| 105 | } |
| 106 | |
| 107 | char * |
| 108 | octet_string_hex_string(const void *s, int length) { |
| 109 | const uint8_t *str = (const uint8_t *)s; |
| 110 | int i; |
| 111 | |
| 112 | /* double length, since one octet takes two hex characters */ |
| 113 | length *= 2; |
| 114 | |
| 115 | /* truncate string if it would be too long */ |
| 116 | if (length > MAX_PRINT_STRING_LEN) |
| 117 | length = MAX_PRINT_STRING_LEN-1; |
| 118 | |
| 119 | for (i=0; i < length; i+=2) { |
| 120 | bit_string[i] = nibble_to_hex_char(*str >> 4); |
| 121 | bit_string[i+1] = nibble_to_hex_char(*str++ & 0xF); |
| 122 | } |
| 123 | bit_string[i] = 0; /* null terminate string */ |
| 124 | return bit_string; |
| 125 | } |
| 126 | |
| 127 | static inline int |
| 128 | hex_char_to_nibble(uint8_t c) { |
| 129 | switch(c) { |
| 130 | case ('0'): return 0x0; |
| 131 | case ('1'): return 0x1; |
| 132 | case ('2'): return 0x2; |
| 133 | case ('3'): return 0x3; |
| 134 | case ('4'): return 0x4; |
| 135 | case ('5'): return 0x5; |
| 136 | case ('6'): return 0x6; |
| 137 | case ('7'): return 0x7; |
| 138 | case ('8'): return 0x8; |
| 139 | case ('9'): return 0x9; |
| 140 | case ('a'): return 0xa; |
| 141 | case ('A'): return 0xa; |
| 142 | case ('b'): return 0xb; |
| 143 | case ('B'): return 0xb; |
| 144 | case ('c'): return 0xc; |
| 145 | case ('C'): return 0xc; |
| 146 | case ('d'): return 0xd; |
| 147 | case ('D'): return 0xd; |
| 148 | case ('e'): return 0xe; |
| 149 | case ('E'): return 0xe; |
| 150 | case ('f'): return 0xf; |
| 151 | case ('F'): return 0xf; |
| 152 | default: break; /* this flags an error */ |
| 153 | } |
| 154 | return -1; |
| 155 | } |
| 156 | |
| 157 | int |
| 158 | is_hex_string(char *s) { |
| 159 | while(*s != 0) |
| 160 | if (hex_char_to_nibble(*s++) == -1) |
| 161 | return 0; |
| 162 | return 1; |
| 163 | } |
| 164 | |
| 165 | /* |
| 166 | * hex_string_to_octet_string converts a hexadecimal string |
| 167 | * of length 2 * len to a raw octet string of length len |
| 168 | */ |
| 169 | |
| 170 | int |
| 171 | hex_string_to_octet_string(char *raw, char *hex, int len) { |
| 172 | uint8_t x; |
| 173 | int tmp; |
| 174 | int hex_len; |
| 175 | |
| 176 | hex_len = 0; |
| 177 | while (hex_len < len) { |
| 178 | tmp = hex_char_to_nibble(hex[0]); |
| 179 | if (tmp == -1) |
| 180 | return hex_len; |
| 181 | x = (tmp << 4); |
| 182 | hex_len++; |
| 183 | tmp = hex_char_to_nibble(hex[1]); |
| 184 | if (tmp == -1) |
| 185 | return hex_len; |
| 186 | x |= (tmp & 0xff); |
| 187 | hex_len++; |
| 188 | *raw++ = x; |
| 189 | hex += 2; |
| 190 | } |
| 191 | return hex_len; |
| 192 | } |
| 193 | |
| 194 | char * |
| 195 | v128_hex_string(v128_t *x) { |
| 196 | int i, j; |
| 197 | |
| 198 | for (i=j=0; i < 16; i++) { |
| 199 | bit_string[j++] = nibble_to_hex_char(x->v8[i] >> 4); |
| 200 | bit_string[j++] = nibble_to_hex_char(x->v8[i] & 0xF); |
| 201 | } |
| 202 | |
| 203 | bit_string[j] = 0; /* null terminate string */ |
| 204 | return bit_string; |
| 205 | } |
| 206 | |
| 207 | char * |
| 208 | v128_bit_string(v128_t *x) { |
| 209 | int j, index; |
| 210 | uint32_t mask; |
| 211 | |
| 212 | for (j=index=0; j < 4; j++) { |
| 213 | for (mask=0x80000000; mask > 0; mask >>= 1) { |
| 214 | if (x->v32[j] & mask) |
| 215 | bit_string[index] = '1'; |
| 216 | else |
| 217 | bit_string[index] = '0'; |
| 218 | ++index; |
| 219 | } |
| 220 | } |
| 221 | bit_string[128] = 0; /* null terminate string */ |
| 222 | |
| 223 | return bit_string; |
| 224 | } |
| 225 | |
| 226 | void |
| 227 | v128_copy_octet_string(v128_t *x, const uint8_t s[16]) { |
| 228 | #ifdef ALIGNMENT_32BIT_REQUIRED |
| 229 | if ((((uint32_t) &s[0]) & 0x3) != 0) |
| 230 | #endif |
| 231 | { |
| 232 | x->v8[0] = s[0]; |
| 233 | x->v8[1] = s[1]; |
| 234 | x->v8[2] = s[2]; |
| 235 | x->v8[3] = s[3]; |
| 236 | x->v8[4] = s[4]; |
| 237 | x->v8[5] = s[5]; |
| 238 | x->v8[6] = s[6]; |
| 239 | x->v8[7] = s[7]; |
| 240 | x->v8[8] = s[8]; |
| 241 | x->v8[9] = s[9]; |
| 242 | x->v8[10] = s[10]; |
| 243 | x->v8[11] = s[11]; |
| 244 | x->v8[12] = s[12]; |
| 245 | x->v8[13] = s[13]; |
| 246 | x->v8[14] = s[14]; |
| 247 | x->v8[15] = s[15]; |
| 248 | } |
| 249 | #ifdef ALIGNMENT_32BIT_REQUIRED |
| 250 | else |
| 251 | { |
| 252 | v128_t *v = (v128_t *) &s[0]; |
| 253 | |
| 254 | v128_copy(x,v); |
| 255 | } |
| 256 | #endif |
| 257 | } |
| 258 | |
| 259 | #ifndef DATATYPES_USE_MACROS /* little functions are not macros */ |
| 260 | |
| 261 | void |
| 262 | v128_set_to_zero(v128_t *x) { |
| 263 | _v128_set_to_zero(x); |
| 264 | } |
| 265 | |
| 266 | void |
| 267 | v128_copy(v128_t *x, const v128_t *y) { |
| 268 | _v128_copy(x, y); |
| 269 | } |
| 270 | |
| 271 | void |
| 272 | v128_xor(v128_t *z, v128_t *x, v128_t *y) { |
| 273 | _v128_xor(z, x, y); |
| 274 | } |
| 275 | |
| 276 | void |
| 277 | v128_and(v128_t *z, v128_t *x, v128_t *y) { |
| 278 | _v128_and(z, x, y); |
| 279 | } |
| 280 | |
| 281 | void |
| 282 | v128_or(v128_t *z, v128_t *x, v128_t *y) { |
| 283 | _v128_or(z, x, y); |
| 284 | } |
| 285 | |
| 286 | void |
| 287 | v128_complement(v128_t *x) { |
| 288 | _v128_complement(x); |
| 289 | } |
| 290 | |
| 291 | int |
| 292 | v128_is_eq(const v128_t *x, const v128_t *y) { |
| 293 | return _v128_is_eq(x, y); |
| 294 | } |
| 295 | |
| 296 | int |
| 297 | v128_xor_eq(v128_t *x, const v128_t *y) { |
| 298 | return _v128_xor_eq(x, y); |
| 299 | } |
| 300 | |
| 301 | int |
| 302 | v128_get_bit(const v128_t *x, int i) { |
| 303 | return _v128_get_bit(x, i); |
| 304 | } |
| 305 | |
| 306 | void |
| 307 | v128_set_bit(v128_t *x, int i) { |
| 308 | _v128_set_bit(x, i); |
| 309 | } |
| 310 | |
| 311 | void |
| 312 | v128_clear_bit(v128_t *x, int i){ |
| 313 | _v128_clear_bit(x, i); |
| 314 | } |
| 315 | |
| 316 | void |
| 317 | v128_set_bit_to(v128_t *x, int i, int y){ |
| 318 | _v128_set_bit_to(x, i, y); |
| 319 | } |
| 320 | |
| 321 | |
| 322 | #endif /* DATATYPES_USE_MACROS */ |
| 323 | |
| 324 | void |
| 325 | v128_right_shift(v128_t *x, int index) { |
| 326 | const int base_index = index >> 5; |
| 327 | const int bit_index = index & 31; |
| 328 | int i, from; |
| 329 | uint32_t b; |
| 330 | |
| 331 | if (index > 127) { |
| 332 | v128_set_to_zero(x); |
| 333 | return; |
| 334 | } |
| 335 | |
| 336 | if (bit_index == 0) { |
| 337 | |
| 338 | /* copy each word from left size to right side */ |
| 339 | x->v32[4-1] = x->v32[4-1-base_index]; |
| 340 | for (i=4-1; i > base_index; i--) |
| 341 | x->v32[i-1] = x->v32[i-1-base_index]; |
| 342 | |
| 343 | } else { |
| 344 | |
| 345 | /* set each word to the "or" of the two bit-shifted words */ |
| 346 | for (i = 4; i > base_index; i--) { |
| 347 | from = i-1 - base_index; |
| 348 | b = x->v32[from] << bit_index; |
| 349 | if (from > 0) |
| 350 | b |= x->v32[from-1] >> (32-bit_index); |
| 351 | x->v32[i-1] = b; |
| 352 | } |
| 353 | |
| 354 | } |
| 355 | |
| 356 | /* now wrap up the final portion */ |
| 357 | for (i=0; i < base_index; i++) |
| 358 | x->v32[i] = 0; |
| 359 | |
| 360 | } |
| 361 | |
| 362 | void |
| 363 | v128_left_shift(v128_t *x, int index) { |
| 364 | int i; |
| 365 | const int base_index = index >> 5; |
| 366 | const int bit_index = index & 31; |
| 367 | |
| 368 | if (index > 127) { |
| 369 | v128_set_to_zero(x); |
| 370 | return; |
| 371 | } |
| 372 | |
| 373 | if (bit_index == 0) { |
| 374 | for (i=0; i < 4 - base_index; i++) |
| 375 | x->v32[i] = x->v32[i+base_index]; |
| 376 | } else { |
| 377 | for (i=0; i < 4 - base_index - 1; i++) |
| 378 | x->v32[i] = (x->v32[i+base_index] >> bit_index) ^ |
| 379 | (x->v32[i+base_index+1] << (32 - bit_index)); |
| 380 | x->v32[4 - base_index-1] = x->v32[4-1] >> bit_index; |
| 381 | } |
| 382 | |
| 383 | /* now wrap up the final portion */ |
| 384 | for (i = 4 - base_index; i < 4; i++) |
| 385 | x->v32[i] = 0; |
| 386 | |
| 387 | } |
| 388 | |
| 389 | |
| 390 | int |
| 391 | octet_string_is_eq(uint8_t *a, uint8_t *b, int len) { |
| 392 | uint8_t *end = b + len; |
| 393 | while (b < end) |
| 394 | if (*a++ != *b++) |
| 395 | return 1; |
| 396 | return 0; |
| 397 | } |
| 398 | |
| 399 | void |
| 400 | octet_string_set_to_zero(uint8_t *s, int len) { |
| 401 | uint8_t *end = s + len; |
| 402 | |
| 403 | do { |
| 404 | *s = 0; |
| 405 | } while (++s < end); |
| 406 | |
| 407 | } |
| 408 | |
| 409 | |
| 410 | /* |
| 411 | * From RFC 1521: The Base64 Alphabet |
| 412 | * |
| 413 | * Value Encoding Value Encoding Value Encoding Value Encoding |
| 414 | * 0 A 17 R 34 i 51 z |
| 415 | * 1 B 18 S 35 j 52 0 |
| 416 | * 2 C 19 T 36 k 53 1 |
| 417 | * 3 D 20 U 37 l 54 2 |
| 418 | * 4 E 21 V 38 m 55 3 |
| 419 | * 5 F 22 W 39 n 56 4 |
| 420 | * 6 G 23 X 40 o 57 5 |
| 421 | * 7 H 24 Y 41 p 58 6 |
| 422 | * 8 I 25 Z 42 q 59 7 |
| 423 | * 9 J 26 a 43 r 60 8 |
| 424 | * 10 K 27 b 44 s 61 9 |
| 425 | * 11 L 28 c 45 t 62 + |
| 426 | * 12 M 29 d 46 u 63 / |
| 427 | * 13 N 30 e 47 v |
| 428 | * 14 O 31 f 48 w (pad) = |
| 429 | * 15 P 32 g 49 x |
| 430 | * 16 Q 33 h 50 y |
| 431 | */ |
| 432 | |
| 433 | int |
| 434 | base64_char_to_sextet(uint8_t c) { |
| 435 | switch(c) { |
| 436 | case 'A': |
| 437 | return 0; |
| 438 | case 'B': |
| 439 | return 1; |
| 440 | case 'C': |
| 441 | return 2; |
| 442 | case 'D': |
| 443 | return 3; |
| 444 | case 'E': |
| 445 | return 4; |
| 446 | case 'F': |
| 447 | return 5; |
| 448 | case 'G': |
| 449 | return 6; |
| 450 | case 'H': |
| 451 | return 7; |
| 452 | case 'I': |
| 453 | return 8; |
| 454 | case 'J': |
| 455 | return 9; |
| 456 | case 'K': |
| 457 | return 10; |
| 458 | case 'L': |
| 459 | return 11; |
| 460 | case 'M': |
| 461 | return 12; |
| 462 | case 'N': |
| 463 | return 13; |
| 464 | case 'O': |
| 465 | return 14; |
| 466 | case 'P': |
| 467 | return 15; |
| 468 | case 'Q': |
| 469 | return 16; |
| 470 | case 'R': |
| 471 | return 17; |
| 472 | case 'S': |
| 473 | return 18; |
| 474 | case 'T': |
| 475 | return 19; |
| 476 | case 'U': |
| 477 | return 20; |
| 478 | case 'V': |
| 479 | return 21; |
| 480 | case 'W': |
| 481 | return 22; |
| 482 | case 'X': |
| 483 | return 23; |
| 484 | case 'Y': |
| 485 | return 24; |
| 486 | case 'Z': |
| 487 | return 25; |
| 488 | case 'a': |
| 489 | return 26; |
| 490 | case 'b': |
| 491 | return 27; |
| 492 | case 'c': |
| 493 | return 28; |
| 494 | case 'd': |
| 495 | return 29; |
| 496 | case 'e': |
| 497 | return 30; |
| 498 | case 'f': |
| 499 | return 31; |
| 500 | case 'g': |
| 501 | return 32; |
| 502 | case 'h': |
| 503 | return 33; |
| 504 | case 'i': |
| 505 | return 34; |
| 506 | case 'j': |
| 507 | return 35; |
| 508 | case 'k': |
| 509 | return 36; |
| 510 | case 'l': |
| 511 | return 37; |
| 512 | case 'm': |
| 513 | return 38; |
| 514 | case 'n': |
| 515 | return 39; |
| 516 | case 'o': |
| 517 | return 40; |
| 518 | case 'p': |
| 519 | return 41; |
| 520 | case 'q': |
| 521 | return 42; |
| 522 | case 'r': |
| 523 | return 43; |
| 524 | case 's': |
| 525 | return 44; |
| 526 | case 't': |
| 527 | return 45; |
| 528 | case 'u': |
| 529 | return 46; |
| 530 | case 'v': |
| 531 | return 47; |
| 532 | case 'w': |
| 533 | return 48; |
| 534 | case 'x': |
| 535 | return 49; |
| 536 | case 'y': |
| 537 | return 50; |
| 538 | case 'z': |
| 539 | return 51; |
| 540 | case '0': |
| 541 | return 52; |
| 542 | case '1': |
| 543 | return 53; |
| 544 | case '2': |
| 545 | return 54; |
| 546 | case '3': |
| 547 | return 55; |
| 548 | case '4': |
| 549 | return 56; |
| 550 | case '5': |
| 551 | return 57; |
| 552 | case '6': |
| 553 | return 58; |
| 554 | case '7': |
| 555 | return 59; |
| 556 | case '8': |
| 557 | return 60; |
| 558 | case '9': |
| 559 | return 61; |
| 560 | case '+': |
| 561 | return 62; |
| 562 | case '/': |
| 563 | return 63; |
| 564 | case '=': |
| 565 | return 64; |
| 566 | default: |
| 567 | break; |
| 568 | } |
| 569 | return -1; |
| 570 | } |
| 571 | |
| 572 | /* |
| 573 | * base64_string_to_octet_string converts a hexadecimal string |
| 574 | * of length 2 * len to a raw octet string of length len |
| 575 | */ |
| 576 | |
| 577 | int |
| 578 | base64_string_to_octet_string(char *raw, char *base64, int len) { |
| 579 | uint8_t x; |
| 580 | int tmp; |
| 581 | int base64_len; |
| 582 | |
| 583 | base64_len = 0; |
| 584 | while (base64_len < len) { |
| 585 | tmp = base64_char_to_sextet(base64[0]); |
| 586 | if (tmp == -1) |
| 587 | return base64_len; |
| 588 | x = (tmp << 6); |
| 589 | base64_len++; |
| 590 | tmp = base64_char_to_sextet(base64[1]); |
| 591 | if (tmp == -1) |
| 592 | return base64_len; |
| 593 | x |= (tmp & 0xffff); |
| 594 | base64_len++; |
| 595 | *raw++ = x; |
| 596 | base64 += 2; |
| 597 | } |
| 598 | return base64_len; |
| 599 | } |