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
octet_get_weight(uint8_t octet)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
nibble_to_hex_char(uint8_t nibble)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 *
octet_string_hex_string(const void * s,int length)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
hex_char_to_nibble(uint8_t c)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
is_hex_string(char * s)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
hex_string_to_octet_string(char * raw,char * hex,int len)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 *
v128_hex_string(v128_t * x)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 *
v128_bit_string(v128_t * x)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
v128_copy_octet_string(v128_t * x,const uint8_t s[16])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
v128_set_to_zero(v128_t * x)263 v128_set_to_zero(v128_t *x) {
264 _v128_set_to_zero(x);
265 }
266
267 void
v128_copy(v128_t * x,const v128_t * y)268 v128_copy(v128_t *x, const v128_t *y) {
269 _v128_copy(x, y);
270 }
271
272 void
v128_xor(v128_t * z,v128_t * x,v128_t * y)273 v128_xor(v128_t *z, v128_t *x, v128_t *y) {
274 _v128_xor(z, x, y);
275 }
276
277 void
v128_and(v128_t * z,v128_t * x,v128_t * y)278 v128_and(v128_t *z, v128_t *x, v128_t *y) {
279 _v128_and(z, x, y);
280 }
281
282 void
v128_or(v128_t * z,v128_t * x,v128_t * y)283 v128_or(v128_t *z, v128_t *x, v128_t *y) {
284 _v128_or(z, x, y);
285 }
286
287 void
v128_complement(v128_t * x)288 v128_complement(v128_t *x) {
289 _v128_complement(x);
290 }
291
292 int
v128_is_eq(const v128_t * x,const v128_t * y)293 v128_is_eq(const v128_t *x, const v128_t *y) {
294 return _v128_is_eq(x, y);
295 }
296
297 int
v128_xor_eq(v128_t * x,const v128_t * y)298 v128_xor_eq(v128_t *x, const v128_t *y) {
299 return _v128_xor_eq(x, y);
300 }
301
302 int
v128_get_bit(const v128_t * x,int i)303 v128_get_bit(const v128_t *x, int i) {
304 return _v128_get_bit(x, i);
305 }
306
307 void
v128_set_bit(v128_t * x,int i)308 v128_set_bit(v128_t *x, int i) {
309 _v128_set_bit(x, i);
310 }
311
312 void
v128_clear_bit(v128_t * x,int i)313 v128_clear_bit(v128_t *x, int i){
314 _v128_clear_bit(x, i);
315 }
316
317 void
v128_set_bit_to(v128_t * x,int i,int y)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
v128_right_shift(v128_t * x,int index)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
v128_left_shift(v128_t * x,int index)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
bitvector_get_bit(const bitvector_t * v,int bit_index)395 bitvector_get_bit(const bitvector_t *v, int bit_index)
396 {
397 return _bitvector_get_bit(v, bit_index);
398 }
399
400 void
bitvector_set_bit(bitvector_t * v,int bit_index)401 bitvector_set_bit(bitvector_t *v, int bit_index)
402 {
403 _bitvector_set_bit(v, bit_index);
404 }
405
406 void
bitvector_clear_bit(bitvector_t * v,int bit_index)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
bitvector_alloc(bitvector_t * v,unsigned long length)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
bitvector_dealloc(bitvector_t * v)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
bitvector_set_to_zero(bitvector_t * x)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 *
bitvector_bit_string(bitvector_t * x,char * buf,int len)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
bitvector_left_shift(bitvector_t * x,int index)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
octet_string_is_eq(uint8_t * a,uint8_t * b,int len)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
octet_string_set_to_zero(uint8_t * s,int len)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
base64_char_to_sextet(uint8_t c)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
base64_string_to_octet_string(char * raw,char * base64,int len)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