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 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: return -1; /* this flags an error */ 153 } 154 /* NOTREACHED */ 155 return -1; /* this keeps compilers from complaining */ 156 } 157 158 int 159 is_hex_string(char *s) { 160 while(*s != 0) 161 if (hex_char_to_nibble(*s++) == -1) 162 return 0; 163 return 1; 164 } 165 166 /* 167 * hex_string_to_octet_string converts a hexadecimal string 168 * of length 2 * len to a raw octet string of length len 169 */ 170 171 int 172 hex_string_to_octet_string(char *raw, char *hex, int len) { 173 uint8_t x; 174 int tmp; 175 int hex_len; 176 177 hex_len = 0; 178 while (hex_len < len) { 179 tmp = hex_char_to_nibble(hex[0]); 180 if (tmp == -1) 181 return hex_len; 182 x = (tmp << 4); 183 hex_len++; 184 tmp = hex_char_to_nibble(hex[1]); 185 if (tmp == -1) 186 return hex_len; 187 x |= (tmp & 0xff); 188 hex_len++; 189 *raw++ = x; 190 hex += 2; 191 } 192 return hex_len; 193 } 194 195 char * 196 v128_hex_string(v128_t *x) { 197 int i, j; 198 199 for (i=j=0; i < 16; i++) { 200 bit_string[j++] = nibble_to_hex_char(x->v8[i] >> 4); 201 bit_string[j++] = nibble_to_hex_char(x->v8[i] & 0xF); 202 } 203 204 bit_string[j] = 0; /* null terminate string */ 205 return bit_string; 206 } 207 208 char * 209 v128_bit_string(v128_t *x) { 210 int j, index; 211 uint32_t mask; 212 213 for (j=index=0; j < 4; j++) { 214 for (mask=0x80000000; mask > 0; mask >>= 1) { 215 if (x->v32[j] & mask) 216 bit_string[index] = '1'; 217 else 218 bit_string[index] = '0'; 219 ++index; 220 } 221 } 222 bit_string[128] = 0; /* null terminate string */ 223 224 return bit_string; 225 } 226 227 void 228 v128_copy_octet_string(v128_t *x, const uint8_t s[16]) { 229 #ifdef ALIGNMENT_32BIT_REQUIRED 230 if ((((uint32_t) &s[0]) & 0x3) != 0) 231 #endif 232 { 233 x->v8[0] = s[0]; 234 x->v8[1] = s[1]; 235 x->v8[2] = s[2]; 236 x->v8[3] = s[3]; 237 x->v8[4] = s[4]; 238 x->v8[5] = s[5]; 239 x->v8[6] = s[6]; 240 x->v8[7] = s[7]; 241 x->v8[8] = s[8]; 242 x->v8[9] = s[9]; 243 x->v8[10] = s[10]; 244 x->v8[11] = s[11]; 245 x->v8[12] = s[12]; 246 x->v8[13] = s[13]; 247 x->v8[14] = s[14]; 248 x->v8[15] = s[15]; 249 } 250 #ifdef ALIGNMENT_32BIT_REQUIRED 251 else 252 { 253 v128_t *v = (v128_t *) &s[0]; 254 255 v128_copy(x,v); 256 } 257 #endif 258 } 259 260 #ifndef DATATYPES_USE_MACROS /* little functions are not macros */ 261 262 void 263 v128_set_to_zero(v128_t *x) { 264 _v128_set_to_zero(x); 265 } 266 267 void 268 v128_copy(v128_t *x, const v128_t *y) { 269 _v128_copy(x, y); 270 } 271 272 void 273 v128_xor(v128_t *z, v128_t *x, v128_t *y) { 274 _v128_xor(z, x, y); 275 } 276 277 void 278 v128_and(v128_t *z, v128_t *x, v128_t *y) { 279 _v128_and(z, x, y); 280 } 281 282 void 283 v128_or(v128_t *z, v128_t *x, v128_t *y) { 284 _v128_or(z, x, y); 285 } 286 287 void 288 v128_complement(v128_t *x) { 289 _v128_complement(x); 290 } 291 292 int 293 v128_is_eq(const v128_t *x, const v128_t *y) { 294 return _v128_is_eq(x, y); 295 } 296 297 int 298 v128_xor_eq(v128_t *x, const v128_t *y) { 299 return _v128_xor_eq(x, y); 300 } 301 302 int 303 v128_get_bit(const v128_t *x, int i) { 304 return _v128_get_bit(x, i); 305 } 306 307 void 308 v128_set_bit(v128_t *x, int i) { 309 _v128_set_bit(x, i); 310 } 311 312 void 313 v128_clear_bit(v128_t *x, int i){ 314 _v128_clear_bit(x, i); 315 } 316 317 void 318 v128_set_bit_to(v128_t *x, int i, int y){ 319 _v128_set_bit_to(x, i, y); 320 } 321 322 323 #endif /* DATATYPES_USE_MACROS */ 324 325 void 326 v128_right_shift(v128_t *x, int index) { 327 const int base_index = index >> 5; 328 const int bit_index = index & 31; 329 int i, from; 330 uint32_t b; 331 332 if (index > 127) { 333 v128_set_to_zero(x); 334 return; 335 } 336 337 if (bit_index == 0) { 338 339 /* copy each word from left size to right side */ 340 x->v32[4-1] = x->v32[4-1-base_index]; 341 for (i=4-1; i > base_index; i--) 342 x->v32[i-1] = x->v32[i-1-base_index]; 343 344 } else { 345 346 /* set each word to the "or" of the two bit-shifted words */ 347 for (i = 4; i > base_index; i--) { 348 from = i-1 - base_index; 349 b = x->v32[from] << bit_index; 350 if (from > 0) 351 b |= x->v32[from-1] >> (32-bit_index); 352 x->v32[i-1] = b; 353 } 354 355 } 356 357 /* now wrap up the final portion */ 358 for (i=0; i < base_index; i++) 359 x->v32[i] = 0; 360 361 } 362 363 void 364 v128_left_shift(v128_t *x, int index) { 365 int i; 366 const int base_index = index >> 5; 367 const int bit_index = index & 31; 368 369 if (index > 127) { 370 v128_set_to_zero(x); 371 return; 372 } 373 374 if (bit_index == 0) { 375 for (i=0; i < 4 - base_index; i++) 376 x->v32[i] = x->v32[i+base_index]; 377 } else { 378 for (i=0; i < 4 - base_index - 1; i++) 379 x->v32[i] = (x->v32[i+base_index] >> bit_index) ^ 380 (x->v32[i+base_index+1] << (32 - bit_index)); 381 x->v32[4 - base_index-1] = x->v32[4-1] >> bit_index; 382 } 383 384 /* now wrap up the final portion */ 385 for (i = 4 - base_index; i < 4; i++) 386 x->v32[i] = 0; 387 388 } 389 390 /* functions manipulating bitvector_t */ 391 392 #ifndef DATATYPES_USE_MACROS /* little functions are not macros */ 393 394 int 395 bitvector_get_bit(const bitvector_t *v, int bit_index) 396 { 397 return _bitvector_get_bit(v, bit_index); 398 } 399 400 void 401 bitvector_set_bit(bitvector_t *v, int bit_index) 402 { 403 _bitvector_set_bit(v, bit_index); 404 } 405 406 void 407 bitvector_clear_bit(bitvector_t *v, int bit_index) 408 { 409 _bitvector_clear_bit(v, bit_index); 410 } 411 412 413 #endif /* DATATYPES_USE_MACROS */ 414 415 int 416 bitvector_alloc(bitvector_t *v, unsigned long length) { 417 unsigned long l; 418 419 /* Round length up to a multiple of bits_per_word */ 420 length = (length + bits_per_word - 1) & ~(unsigned long)((bits_per_word - 1)); 421 422 l = length / bits_per_word * bytes_per_word; 423 424 /* allocate memory, then set parameters */ 425 if (l == 0) 426 v->word = NULL; 427 else { 428 v->word = (uint32_t*)crypto_alloc(l); 429 if (v->word == NULL) { 430 v->word = NULL; 431 v->length = 0; 432 return -1; 433 } 434 } 435 v->length = length; 436 437 /* initialize bitvector to zero */ 438 bitvector_set_to_zero(v); 439 440 return 0; 441 } 442 443 444 void 445 bitvector_dealloc(bitvector_t *v) { 446 if (v->word != NULL) 447 crypto_free(v->word); 448 v->word = NULL; 449 v->length = 0; 450 } 451 452 void 453 bitvector_set_to_zero(bitvector_t *x) 454 { 455 /* C99 guarantees that memset(0) will set the value 0 for uint32_t */ 456 memset(x->word, 0, x->length >> 3); 457 } 458 459 char * 460 bitvector_bit_string(bitvector_t *x, char* buf, int len) { 461 int j, index; 462 uint32_t mask; 463 464 for (j=index=0; j < (int)(x->length>>5) && index < len-1; j++) { 465 for (mask=0x80000000; mask > 0; mask >>= 1) { 466 if (x->word[j] & mask) 467 buf[index] = '1'; 468 else 469 buf[index] = '0'; 470 ++index; 471 if (index >= len-1) 472 break; 473 } 474 } 475 buf[index] = 0; /* null terminate string */ 476 477 return buf; 478 } 479 480 void 481 bitvector_left_shift(bitvector_t *x, int index) { 482 int i; 483 const int base_index = index >> 5; 484 const int bit_index = index & 31; 485 const int word_length = x->length >> 5; 486 487 if (index >= (int)x->length) { 488 bitvector_set_to_zero(x); 489 return; 490 } 491 492 if (bit_index == 0) { 493 for (i=0; i < word_length - base_index; i++) 494 x->word[i] = x->word[i+base_index]; 495 } else { 496 for (i=0; i < word_length - base_index - 1; i++) 497 x->word[i] = (x->word[i+base_index] >> bit_index) ^ 498 (x->word[i+base_index+1] << (32 - bit_index)); 499 x->word[word_length - base_index-1] = x->word[word_length-1] >> bit_index; 500 } 501 502 /* now wrap up the final portion */ 503 for (i = word_length - base_index; i < word_length; i++) 504 x->word[i] = 0; 505 506 } 507 508 509 int 510 octet_string_is_eq(uint8_t *a, uint8_t *b, int len) { 511 uint8_t *end = b + len; 512 while (b < end) 513 if (*a++ != *b++) 514 return 1; 515 return 0; 516 } 517 518 void 519 octet_string_set_to_zero(uint8_t *s, int len) { 520 uint8_t *end = s + len; 521 522 do { 523 *s = 0; 524 } while (++s < end); 525 526 } 527 528 529 /* 530 * From RFC 1521: The Base64 Alphabet 531 * 532 * Value Encoding Value Encoding Value Encoding Value Encoding 533 * 0 A 17 R 34 i 51 z 534 * 1 B 18 S 35 j 52 0 535 * 2 C 19 T 36 k 53 1 536 * 3 D 20 U 37 l 54 2 537 * 4 E 21 V 38 m 55 3 538 * 5 F 22 W 39 n 56 4 539 * 6 G 23 X 40 o 57 5 540 * 7 H 24 Y 41 p 58 6 541 * 8 I 25 Z 42 q 59 7 542 * 9 J 26 a 43 r 60 8 543 * 10 K 27 b 44 s 61 9 544 * 11 L 28 c 45 t 62 + 545 * 12 M 29 d 46 u 63 / 546 * 13 N 30 e 47 v 547 * 14 O 31 f 48 w (pad) = 548 * 15 P 32 g 49 x 549 * 16 Q 33 h 50 y 550 */ 551 552 int 553 base64_char_to_sextet(uint8_t c) { 554 switch(c) { 555 case 'A': 556 return 0; 557 case 'B': 558 return 1; 559 case 'C': 560 return 2; 561 case 'D': 562 return 3; 563 case 'E': 564 return 4; 565 case 'F': 566 return 5; 567 case 'G': 568 return 6; 569 case 'H': 570 return 7; 571 case 'I': 572 return 8; 573 case 'J': 574 return 9; 575 case 'K': 576 return 10; 577 case 'L': 578 return 11; 579 case 'M': 580 return 12; 581 case 'N': 582 return 13; 583 case 'O': 584 return 14; 585 case 'P': 586 return 15; 587 case 'Q': 588 return 16; 589 case 'R': 590 return 17; 591 case 'S': 592 return 18; 593 case 'T': 594 return 19; 595 case 'U': 596 return 20; 597 case 'V': 598 return 21; 599 case 'W': 600 return 22; 601 case 'X': 602 return 23; 603 case 'Y': 604 return 24; 605 case 'Z': 606 return 25; 607 case 'a': 608 return 26; 609 case 'b': 610 return 27; 611 case 'c': 612 return 28; 613 case 'd': 614 return 29; 615 case 'e': 616 return 30; 617 case 'f': 618 return 31; 619 case 'g': 620 return 32; 621 case 'h': 622 return 33; 623 case 'i': 624 return 34; 625 case 'j': 626 return 35; 627 case 'k': 628 return 36; 629 case 'l': 630 return 37; 631 case 'm': 632 return 38; 633 case 'n': 634 return 39; 635 case 'o': 636 return 40; 637 case 'p': 638 return 41; 639 case 'q': 640 return 42; 641 case 'r': 642 return 43; 643 case 's': 644 return 44; 645 case 't': 646 return 45; 647 case 'u': 648 return 46; 649 case 'v': 650 return 47; 651 case 'w': 652 return 48; 653 case 'x': 654 return 49; 655 case 'y': 656 return 50; 657 case 'z': 658 return 51; 659 case '0': 660 return 52; 661 case '1': 662 return 53; 663 case '2': 664 return 54; 665 case '3': 666 return 55; 667 case '4': 668 return 56; 669 case '5': 670 return 57; 671 case '6': 672 return 58; 673 case '7': 674 return 59; 675 case '8': 676 return 60; 677 case '9': 678 return 61; 679 case '+': 680 return 62; 681 case '/': 682 return 63; 683 case '=': 684 return 64; 685 default: 686 break; 687 } 688 return -1; 689 } 690 691 /* 692 * base64_string_to_octet_string converts a hexadecimal string 693 * of length 2 * len to a raw octet string of length len 694 */ 695 696 int 697 base64_string_to_octet_string(char *raw, char *base64, int len) { 698 uint8_t x; 699 int tmp; 700 int base64_len; 701 702 base64_len = 0; 703 while (base64_len < len) { 704 tmp = base64_char_to_sextet(base64[0]); 705 if (tmp == -1) 706 return base64_len; 707 x = (tmp << 6); 708 base64_len++; 709 tmp = base64_char_to_sextet(base64[1]); 710 if (tmp == -1) 711 return base64_len; 712 x |= (tmp & 0xffff); 713 base64_len++; 714 *raw++ = x; 715 base64 += 2; 716 } 717 return base64_len; 718 } 719
