Home | History | Annotate | Download | only in math
      1 /*
      2  * math.c
      3  *
      4  * crypto math operations and data types
      5  *
      6  * David A. McGrew
      7  * Cisco Systems, Inc.
      8  */
      9 /*
     10  *
     11  * Copyright (c) 2001-2006 Cisco Systems, Inc.
     12  * All rights reserved.
     13  *
     14  * Redistribution and use in source and binary forms, with or without
     15  * modification, are permitted provided that the following conditions
     16  * are met:
     17  *
     18  *   Redistributions of source code must retain the above copyright
     19  *   notice, this list of conditions and the following disclaimer.
     20  *
     21  *   Redistributions in binary form must reproduce the above
     22  *   copyright notice, this list of conditions and the following
     23  *   disclaimer in the documentation and/or other materials provided
     24  *   with the distribution.
     25  *
     26  *   Neither the name of the Cisco Systems, Inc. nor the names of its
     27  *   contributors may be used to endorse or promote products derived
     28  *   from this software without specific prior written permission.
     29  *
     30  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     31  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     32  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
     33  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
     34  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
     35  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
     36  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
     37  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     38  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
     39  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     40  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
     41  * OF THE POSSIBILITY OF SUCH DAMAGE.
     42  *
     43  */
     44 
     45 #include "crypto_math.h"
     46 
     47 int
     48 octet_weight[256] = {
     49   0, 1, 1, 2, 1, 2, 2, 3,
     50   1, 2, 2, 3, 2, 3, 3, 4,
     51   1, 2, 2, 3, 2, 3, 3, 4,
     52   2, 3, 3, 4, 3, 4, 4, 5,
     53   1, 2, 2, 3, 2, 3, 3, 4,
     54   2, 3, 3, 4, 3, 4, 4, 5,
     55   2, 3, 3, 4, 3, 4, 4, 5,
     56   3, 4, 4, 5, 4, 5, 5, 6,
     57   1, 2, 2, 3, 2, 3, 3, 4,
     58   2, 3, 3, 4, 3, 4, 4, 5,
     59   2, 3, 3, 4, 3, 4, 4, 5,
     60   3, 4, 4, 5, 4, 5, 5, 6,
     61   2, 3, 3, 4, 3, 4, 4, 5,
     62   3, 4, 4, 5, 4, 5, 5, 6,
     63   3, 4, 4, 5, 4, 5, 5, 6,
     64   4, 5, 5, 6, 5, 6, 6, 7,
     65   1, 2, 2, 3, 2, 3, 3, 4,
     66   2, 3, 3, 4, 3, 4, 4, 5,
     67   2, 3, 3, 4, 3, 4, 4, 5,
     68   3, 4, 4, 5, 4, 5, 5, 6,
     69   2, 3, 3, 4, 3, 4, 4, 5,
     70   3, 4, 4, 5, 4, 5, 5, 6,
     71   3, 4, 4, 5, 4, 5, 5, 6,
     72   4, 5, 5, 6, 5, 6, 6, 7,
     73   2, 3, 3, 4, 3, 4, 4, 5,
     74   3, 4, 4, 5, 4, 5, 5, 6,
     75   3, 4, 4, 5, 4, 5, 5, 6,
     76   4, 5, 5, 6, 5, 6, 6, 7,
     77   3, 4, 4, 5, 4, 5, 5, 6,
     78   4, 5, 5, 6, 5, 6, 6, 7,
     79   4, 5, 5, 6, 5, 6, 6, 7,
     80   5, 6, 6, 7, 6, 7, 7, 8
     81 };
     82 
     83 int
     84 low_bit[256] = {
     85   -1, 0, 1, 0, 2, 0, 1, 0,
     86   3, 0, 1, 0, 2, 0, 1, 0,
     87   4, 0, 1, 0, 2, 0, 1, 0,
     88   3, 0, 1, 0, 2, 0, 1, 0,
     89   5, 0, 1, 0, 2, 0, 1, 0,
     90   3, 0, 1, 0, 2, 0, 1, 0,
     91   4, 0, 1, 0, 2, 0, 1, 0,
     92   3, 0, 1, 0, 2, 0, 1, 0,
     93   6, 0, 1, 0, 2, 0, 1, 0,
     94   3, 0, 1, 0, 2, 0, 1, 0,
     95   4, 0, 1, 0, 2, 0, 1, 0,
     96   3, 0, 1, 0, 2, 0, 1, 0,
     97   5, 0, 1, 0, 2, 0, 1, 0,
     98   3, 0, 1, 0, 2, 0, 1, 0,
     99   4, 0, 1, 0, 2, 0, 1, 0,
    100   3, 0, 1, 0, 2, 0, 1, 0,
    101   7, 0, 1, 0, 2, 0, 1, 0,
    102   3, 0, 1, 0, 2, 0, 1, 0,
    103   4, 0, 1, 0, 2, 0, 1, 0,
    104   3, 0, 1, 0, 2, 0, 1, 0,
    105   5, 0, 1, 0, 2, 0, 1, 0,
    106   3, 0, 1, 0, 2, 0, 1, 0,
    107   4, 0, 1, 0, 2, 0, 1, 0,
    108   3, 0, 1, 0, 2, 0, 1, 0,
    109   6, 0, 1, 0, 2, 0, 1, 0,
    110   3, 0, 1, 0, 2, 0, 1, 0,
    111   4, 0, 1, 0, 2, 0, 1, 0,
    112   3, 0, 1, 0, 2, 0, 1, 0,
    113   5, 0, 1, 0, 2, 0, 1, 0,
    114   3, 0, 1, 0, 2, 0, 1, 0,
    115   4, 0, 1, 0, 2, 0, 1, 0,
    116   3, 0, 1, 0, 2, 0, 1, 0
    117 };
    118 
    119 
    120 int
    121 high_bit[256] = {
    122   -1, 0, 1, 1, 2, 2, 2, 2,
    123   3, 3, 3, 3, 3, 3, 3, 3,
    124   4, 4, 4, 4, 4, 4, 4, 4,
    125   4, 4, 4, 4, 4, 4, 4, 4,
    126   5, 5, 5, 5, 5, 5, 5, 5,
    127   5, 5, 5, 5, 5, 5, 5, 5,
    128   5, 5, 5, 5, 5, 5, 5, 5,
    129   5, 5, 5, 5, 5, 5, 5, 5,
    130   6, 6, 6, 6, 6, 6, 6, 6,
    131   6, 6, 6, 6, 6, 6, 6, 6,
    132   6, 6, 6, 6, 6, 6, 6, 6,
    133   6, 6, 6, 6, 6, 6, 6, 6,
    134   6, 6, 6, 6, 6, 6, 6, 6,
    135   6, 6, 6, 6, 6, 6, 6, 6,
    136   6, 6, 6, 6, 6, 6, 6, 6,
    137   6, 6, 6, 6, 6, 6, 6, 6,
    138   7, 7, 7, 7, 7, 7, 7, 7,
    139   7, 7, 7, 7, 7, 7, 7, 7,
    140   7, 7, 7, 7, 7, 7, 7, 7,
    141   7, 7, 7, 7, 7, 7, 7, 7,
    142   7, 7, 7, 7, 7, 7, 7, 7,
    143   7, 7, 7, 7, 7, 7, 7, 7,
    144   7, 7, 7, 7, 7, 7, 7, 7,
    145   7, 7, 7, 7, 7, 7, 7, 7,
    146   7, 7, 7, 7, 7, 7, 7, 7,
    147   7, 7, 7, 7, 7, 7, 7, 7,
    148   7, 7, 7, 7, 7, 7, 7, 7,
    149   7, 7, 7, 7, 7, 7, 7, 7,
    150   7, 7, 7, 7, 7, 7, 7, 7,
    151   7, 7, 7, 7, 7, 7, 7, 7,
    152   7, 7, 7, 7, 7, 7, 7, 7,
    153   7, 7, 7, 7, 7, 7, 7, 7
    154 };
    155 
    156 int
    157 octet_get_weight(uint8_t octet) {
    158   extern int octet_weight[256];
    159 
    160   return octet_weight[octet];
    161 }
    162 
    163 unsigned char
    164 v32_weight(v32_t a) {
    165   unsigned int wt = 0;
    166 
    167   wt += octet_weight[a.v8[0]];  /* note: endian-ness makes no difference */
    168   wt += octet_weight[a.v8[1]];
    169   wt += octet_weight[a.v8[2]];
    170   wt += octet_weight[a.v8[3]];
    171 
    172   return wt;
    173 }
    174 
    175 unsigned char
    176 v32_distance(v32_t x, v32_t y) {
    177   x.value ^= y.value;
    178   return v32_weight(x);
    179 }
    180 
    181 unsigned int
    182 v32_dot_product(v32_t a, v32_t b) {
    183   a.value &= b.value;
    184   return v32_weight(a) & 1;
    185 }
    186 
    187 /*
    188  * _bit_string returns a NULL-terminated character string suitable for
    189  * printing
    190  */
    191 
    192 #define MAX_STRING_LENGTH 1024
    193 
    194 char bit_string[MAX_STRING_LENGTH];
    195 
    196 char *
    197 octet_bit_string(uint8_t x) {
    198   int mask, index;
    199 
    200   for (mask = 1, index = 0; mask < 256; mask <<= 1)
    201     if ((x & mask) == 0)
    202       bit_string[index++] = '0';
    203     else
    204       bit_string[index++] = '1';
    205 
    206   bit_string[index++] = 0;  /* NULL terminate string */
    207 
    208   return bit_string;
    209 }
    210 
    211 char *
    212 v16_bit_string(v16_t x) {
    213   int i, mask, index;
    214 
    215   for (i = index = 0; i < 2; i++) {
    216     for (mask = 1; mask < 256; mask <<= 1)
    217       if ((x.v8[i] & mask) == 0)
    218 	bit_string[index++] = '0';
    219       else
    220 	bit_string[index++] = '1';
    221   }
    222   bit_string[index++] = 0;  /* NULL terminate string */
    223   return bit_string;
    224 }
    225 
    226 char *
    227 v32_bit_string(v32_t x) {
    228   int i, mask, index;
    229 
    230   for (i = index = 0; i < 4; i++) {
    231     for (mask = 128; mask > 0; mask >>= 1)
    232       if ((x.v8[i] & mask) == 0)
    233 	bit_string[index++] = '0';
    234       else
    235 	bit_string[index++] = '1';
    236   }
    237   bit_string[index++] = 0;  /* NULL terminate string */
    238   return bit_string;
    239 }
    240 
    241 char *
    242 v64_bit_string(const v64_t *x) {
    243   int i, mask, index;
    244 
    245   for (i = index = 0; i < 8; i++) {
    246     for (mask = 1; mask < 256; mask <<= 1)
    247       if ((x->v8[i] & mask) == 0)
    248 	bit_string[index++] = '0';
    249       else
    250 	bit_string[index++] = '1';
    251   }
    252   bit_string[index++] = 0;  /* NULL terminate string */
    253   return bit_string;
    254 }
    255 
    256 char *
    257 v128_bit_string(v128_t *x) {
    258   int j, index;
    259   uint32_t mask;
    260 
    261   for (j=index=0; j < 4; j++) {
    262     for (mask=0x80000000; mask > 0; mask >>= 1) {
    263       if (x->v32[j] & mask)
    264 	bit_string[index] = '1';
    265       else
    266 	bit_string[index] = '0';
    267       ++index;
    268     }
    269   }
    270   bit_string[128] = 0; /* null terminate string */
    271 
    272   return bit_string;
    273 }
    274 
    275 uint8_t
    276 nibble_to_hex_char(uint8_t nibble) {
    277   char buf[16] = {'0', '1', '2', '3', '4', '5', '6', '7',
    278 		  '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
    279   return buf[nibble & 0xF];
    280 }
    281 
    282 char *
    283 octet_hex_string(uint8_t x) {
    284 
    285   bit_string[0]  = nibble_to_hex_char(x >> 4);
    286   bit_string[1]  = nibble_to_hex_char(x & 0xF);
    287 
    288   bit_string[2] = 0; /* null terminate string */
    289   return bit_string;
    290 }
    291 
    292 char *
    293 octet_string_hex_string(const void *str, int length) {
    294   const uint8_t *s = str;
    295   int i;
    296 
    297   /* double length, since one octet takes two hex characters */
    298   length *= 2;
    299 
    300   /* truncate string if it would be too long */
    301   if (length > MAX_STRING_LENGTH)
    302     length = MAX_STRING_LENGTH-1;
    303 
    304   for (i=0; i < length; i+=2) {
    305     bit_string[i]   = nibble_to_hex_char(*s >> 4);
    306     bit_string[i+1] = nibble_to_hex_char(*s++ & 0xF);
    307   }
    308   bit_string[i] = 0; /* null terminate string */
    309   return bit_string;
    310 }
    311 
    312 char *
    313 v16_hex_string(v16_t x) {
    314   int i, j;
    315 
    316   for (i=j=0; i < 2; i++) {
    317     bit_string[j++]  = nibble_to_hex_char(x.v8[i] >> 4);
    318     bit_string[j++]  = nibble_to_hex_char(x.v8[i] & 0xF);
    319   }
    320 
    321   bit_string[j] = 0; /* null terminate string */
    322   return bit_string;
    323 }
    324 
    325 char *
    326 v32_hex_string(v32_t x) {
    327   int i, j;
    328 
    329   for (i=j=0; i < 4; i++) {
    330     bit_string[j++]  = nibble_to_hex_char(x.v8[i] >> 4);
    331     bit_string[j++]  = nibble_to_hex_char(x.v8[i] & 0xF);
    332   }
    333 
    334   bit_string[j] = 0; /* null terminate string */
    335   return bit_string;
    336 }
    337 
    338 char *
    339 v64_hex_string(const v64_t *x) {
    340   int i, j;
    341 
    342   for (i=j=0; i < 8; i++) {
    343     bit_string[j++]  = nibble_to_hex_char(x->v8[i] >> 4);
    344     bit_string[j++]  = nibble_to_hex_char(x->v8[i] & 0xF);
    345   }
    346 
    347   bit_string[j] = 0; /* null terminate string */
    348   return bit_string;
    349 }
    350 
    351 char *
    352 v128_hex_string(v128_t *x) {
    353   int i, j;
    354 
    355   for (i=j=0; i < 16; i++) {
    356     bit_string[j++]  = nibble_to_hex_char(x->v8[i] >> 4);
    357     bit_string[j++]  = nibble_to_hex_char(x->v8[i] & 0xF);
    358   }
    359 
    360   bit_string[j] = 0; /* null terminate string */
    361   return bit_string;
    362 }
    363 
    364 char *
    365 char_to_hex_string(char *x, int num_char) {
    366   int i, j;
    367 
    368   if (num_char >= 16)
    369     num_char = 16;
    370   for (i=j=0; i < num_char; i++) {
    371     bit_string[j++]  = nibble_to_hex_char(x[i] >> 4);
    372     bit_string[j++]  = nibble_to_hex_char(x[i] & 0xF);
    373   }
    374 
    375   bit_string[j] = 0; /* null terminate string */
    376   return bit_string;
    377 }
    378 
    379 int
    380 hex_char_to_nibble(uint8_t c) {
    381   switch(c) {
    382   case ('0'): return 0x0;
    383   case ('1'): return 0x1;
    384   case ('2'): return 0x2;
    385   case ('3'): return 0x3;
    386   case ('4'): return 0x4;
    387   case ('5'): return 0x5;
    388   case ('6'): return 0x6;
    389   case ('7'): return 0x7;
    390   case ('8'): return 0x8;
    391   case ('9'): return 0x9;
    392   case ('a'): return 0xa;
    393   case ('A'): return 0xa;
    394   case ('b'): return 0xb;
    395   case ('B'): return 0xb;
    396   case ('c'): return 0xc;
    397   case ('C'): return 0xc;
    398   case ('d'): return 0xd;
    399   case ('D'): return 0xd;
    400   case ('e'): return 0xe;
    401   case ('E'): return 0xe;
    402   case ('f'): return 0xf;
    403   case ('F'): return 0xf;
    404   default: return -1;   /* this flags an error */
    405   }
    406   /* NOTREACHED */
    407   return -1;  /* this keeps compilers from complaining */
    408 }
    409 
    410 int
    411 is_hex_string(char *s) {
    412   while(*s != 0)
    413     if (hex_char_to_nibble(*s++) == -1)
    414       return 0;
    415   return 1;
    416 }
    417 
    418 uint8_t
    419 hex_string_to_octet(char *s) {
    420   uint8_t x;
    421 
    422   x = (hex_char_to_nibble(s[0]) << 4)
    423     | hex_char_to_nibble(s[1] & 0xFF);
    424 
    425   return x;
    426 }
    427 
    428 /*
    429  * hex_string_to_octet_string converts a hexadecimal string
    430  * of length 2 * len to a raw octet string of length len
    431  */
    432 
    433 int
    434 hex_string_to_octet_string(char *raw, char *hex, int len) {
    435   uint8_t x;
    436   int tmp;
    437   int hex_len;
    438 
    439   hex_len = 0;
    440   while (hex_len < len) {
    441     tmp = hex_char_to_nibble(hex[0]);
    442     if (tmp == -1)
    443       return hex_len;
    444     x = (tmp << 4);
    445     hex_len++;
    446     tmp = hex_char_to_nibble(hex[1]);
    447     if (tmp == -1)
    448       return hex_len;
    449     x |= (tmp & 0xff);
    450     hex_len++;
    451     *raw++ = x;
    452     hex += 2;
    453   }
    454   return hex_len;
    455 }
    456 
    457 v16_t
    458 hex_string_to_v16(char *s) {
    459   v16_t x;
    460   int i, j;
    461 
    462   for (i=j=0; i < 4; i += 2, j++) {
    463     x.v8[j] = (hex_char_to_nibble(s[i]) << 4)
    464       | hex_char_to_nibble(s[i+1] & 0xFF);
    465   }
    466   return x;
    467 }
    468 
    469 v32_t
    470 hex_string_to_v32(char *s) {
    471   v32_t x;
    472   int i, j;
    473 
    474   for (i=j=0; i < 8; i += 2, j++) {
    475     x.v8[j] = (hex_char_to_nibble(s[i]) << 4)
    476       | hex_char_to_nibble(s[i+1] & 0xFF);
    477   }
    478   return x;
    479 }
    480 
    481 v64_t
    482 hex_string_to_v64(char *s) {
    483   v64_t x;
    484   int i, j;
    485 
    486   for (i=j=0; i < 16; i += 2, j++) {
    487     x.v8[j] = (hex_char_to_nibble(s[i]) << 4)
    488       | hex_char_to_nibble(s[i+1] & 0xFF);
    489   }
    490   return x;
    491 }
    492 
    493 v128_t
    494 hex_string_to_v128(char *s) {
    495   v128_t x;
    496   int i, j;
    497 
    498   for (i=j=0; i < 32; i += 2, j++) {
    499     x.v8[j] = (hex_char_to_nibble(s[i]) << 4)
    500       | hex_char_to_nibble(s[i+1] & 0xFF);
    501   }
    502   return x;
    503 }
    504 
    505 
    506 
    507 /*
    508  * the matrix A[] is stored in column format, i.e., A[i] is the ith
    509  * column of the matrix
    510  */
    511 
    512 uint8_t
    513 A_times_x_plus_b(uint8_t A[8], uint8_t x, uint8_t b) {
    514   int index = 0;
    515   unsigned mask;
    516 
    517   for (mask=1; mask < 256; mask *= 2) {
    518     if (x & mask)
    519       b^= A[index];
    520     ++index;
    521   }
    522 
    523   return b;
    524 }
    525 
    526 void
    527 v16_copy_octet_string(v16_t *x, const uint8_t s[2]) {
    528   x->v8[0]  = s[0];
    529   x->v8[1]  = s[1];
    530 }
    531 
    532 void
    533 v32_copy_octet_string(v32_t *x, const uint8_t s[4]) {
    534   x->v8[0]  = s[0];
    535   x->v8[1]  = s[1];
    536   x->v8[2]  = s[2];
    537   x->v8[3]  = s[3];
    538 }
    539 
    540 void
    541 v64_copy_octet_string(v64_t *x, const uint8_t s[8]) {
    542   x->v8[0]  = s[0];
    543   x->v8[1]  = s[1];
    544   x->v8[2]  = s[2];
    545   x->v8[3]  = s[3];
    546   x->v8[4]  = s[4];
    547   x->v8[5]  = s[5];
    548   x->v8[6]  = s[6];
    549   x->v8[7]  = s[7];
    550 }
    551 
    552 void
    553 v128_copy_octet_string(v128_t *x, const uint8_t s[16]) {
    554   x->v8[0]  = s[0];
    555   x->v8[1]  = s[1];
    556   x->v8[2]  = s[2];
    557   x->v8[3]  = s[3];
    558   x->v8[4]  = s[4];
    559   x->v8[5]  = s[5];
    560   x->v8[6]  = s[6];
    561   x->v8[7]  = s[7];
    562   x->v8[8]  = s[8];
    563   x->v8[9]  = s[9];
    564   x->v8[10] = s[10];
    565   x->v8[11] = s[11];
    566   x->v8[12] = s[12];
    567   x->v8[13] = s[13];
    568   x->v8[14] = s[14];
    569   x->v8[15] = s[15];
    570 
    571 }
    572 
    573 #ifndef DATATYPES_USE_MACROS /* little functions are not macros */
    574 
    575 void
    576 v128_set_to_zero(v128_t *x) {
    577   _v128_set_to_zero(x);
    578 }
    579 
    580 void
    581 v128_copy(v128_t *x, const v128_t *y) {
    582   _v128_copy(x, y);
    583 }
    584 
    585 void
    586 v128_xor(v128_t *z, v128_t *x, v128_t *y) {
    587   _v128_xor(z, x, y);
    588 }
    589 
    590 void
    591 v128_and(v128_t *z, v128_t *x, v128_t *y) {
    592   _v128_and(z, x, y);
    593 }
    594 
    595 void
    596 v128_or(v128_t *z, v128_t *x, v128_t *y) {
    597   _v128_or(z, x, y);
    598 }
    599 
    600 void
    601 v128_complement(v128_t *x) {
    602   _v128_complement(x);
    603 }
    604 
    605 int
    606 v128_is_eq(const v128_t *x, const v128_t *y) {
    607   return _v128_is_eq(x, y);
    608 }
    609 
    610 int
    611 v128_get_bit(const v128_t *x, int i) {
    612   return _v128_get_bit(x, i);
    613 }
    614 
    615 void
    616 v128_set_bit(v128_t *x, int i) {
    617   _v128_set_bit(x, i);
    618 }
    619 
    620 void
    621 v128_clear_bit(v128_t *x, int i){
    622   _v128_clear_bit(x, i);
    623 }
    624 
    625 void
    626 v128_set_bit_to(v128_t *x, int i, int y){
    627   _v128_set_bit_to(x, i, y);
    628 }
    629 
    630 
    631 #endif /* DATATYPES_USE_MACROS */
    632 
    633 
    634 static INLINE void
    635 v128_left_shift2(v128_t *x, int num_bits) {
    636   int i;
    637   int word_shift = num_bits >> 5;
    638   int bit_shift  = num_bits & 31;
    639 
    640   for (i=0; i < (4-word_shift); i++) {
    641     x->v32[i] = x->v32[i+word_shift] << bit_shift;
    642   }
    643 
    644   for (   ; i < word_shift; i++) {
    645     x->v32[i] = 0;
    646   }
    647 
    648 }
    649 
    650 void
    651 v128_right_shift(v128_t *x, int index) {
    652   const int base_index = index >> 5;
    653   const int bit_index = index & 31;
    654   int i, from;
    655   uint32_t b;
    656 
    657   if (index > 127) {
    658     v128_set_to_zero(x);
    659     return;
    660   }
    661 
    662   if (bit_index == 0) {
    663 
    664     /* copy each word from left size to right side */
    665     x->v32[4-1] = x->v32[4-1-base_index];
    666     for (i=4-1; i > base_index; i--)
    667       x->v32[i-1] = x->v32[i-1-base_index];
    668 
    669   } else {
    670 
    671     /* set each word to the "or" of the two bit-shifted words */
    672     for (i = 4; i > base_index; i--) {
    673       from = i-1 - base_index;
    674       b = x->v32[from] << bit_index;
    675       if (from > 0)
    676         b |= x->v32[from-1] >> (32-bit_index);
    677       x->v32[i-1] = b;
    678     }
    679 
    680   }
    681 
    682   /* now wrap up the final portion */
    683   for (i=0; i < base_index; i++)
    684     x->v32[i] = 0;
    685 
    686 }
    687 
    688 void
    689 v128_left_shift(v128_t *x, int index) {
    690   int i;
    691   const int base_index = index >> 5;
    692   const int bit_index = index & 31;
    693 
    694   if (index > 127) {
    695     v128_set_to_zero(x);
    696     return;
    697   }
    698 
    699   if (bit_index == 0) {
    700     for (i=0; i < 4 - base_index; i++)
    701       x->v32[i] = x->v32[i+base_index];
    702   } else {
    703     for (i=0; i < 4 - base_index - 1; i++)
    704       x->v32[i] = (x->v32[i+base_index] << bit_index) ^
    705 	(x->v32[i+base_index+1] >> (32 - bit_index));
    706     x->v32[4 - base_index-1] = x->v32[4-1] << bit_index;
    707   }
    708 
    709   /* now wrap up the final portion */
    710   for (i = 4 - base_index; i < 4; i++)
    711     x->v32[i] = 0;
    712 
    713 }
    714 
    715 
    716 #if 0
    717 void
    718 v128_add(v128_t *z, v128_t *x, v128_t *y) {
    719   /* integer addition modulo 2^128    */
    720 
    721 #ifdef WORDS_BIGENDIAN
    722   uint64_t tmp;
    723 
    724   tmp = x->v32[3] + y->v32[3];
    725   z->v32[3] = (uint32_t) tmp;
    726 
    727   tmp =  x->v32[2] + y->v32[2] + (tmp >> 32);
    728   z->v32[2] = (uint32_t) tmp;
    729 
    730   tmp =  x->v32[1] + y->v32[1] + (tmp >> 32);
    731   z->v32[1] = (uint32_t) tmp;
    732 
    733   tmp =  x->v32[0] + y->v32[0] + (tmp >> 32);
    734   z->v32[0] = (uint32_t) tmp;
    735 
    736 #else /* assume little endian architecture */
    737   uint64_t tmp;
    738 
    739   tmp = htonl(x->v32[3]) + htonl(y->v32[3]);
    740   z->v32[3] = ntohl((uint32_t) tmp);
    741 
    742   tmp =  htonl(x->v32[2]) + htonl(y->v32[2]) + htonl(tmp >> 32);
    743   z->v32[2] = ntohl((uint32_t) tmp);
    744 
    745   tmp =  htonl(x->v32[1]) + htonl(y->v32[1]) + htonl(tmp >> 32);
    746   z->v32[1] = ntohl((uint32_t) tmp);
    747 
    748   tmp =  htonl(x->v32[0]) + htonl(y->v32[0]) + htonl(tmp >> 32);
    749   z->v32[0] = ntohl((uint32_t) tmp);
    750 
    751 #endif /* WORDS_BIGENDIAN */
    752 
    753 }
    754 #endif
    755 
    756 int
    757 octet_string_is_eq(uint8_t *a, uint8_t *b, int len) {
    758   uint8_t *end = b + len;
    759   while (b < end)
    760     if (*a++ != *b++)
    761       return 1;
    762   return 0;
    763 }
    764 
    765 void
    766 octet_string_set_to_zero(uint8_t *s, int len) {
    767   uint8_t *end = s + len;
    768 
    769   do {
    770     *s = 0;
    771   } while (++s < end);
    772 
    773 }
    774 
    775 
    776 /* functions below not yet tested! */
    777 
    778 int
    779 v32_low_bit(v32_t *w) {
    780   int value;
    781 
    782   value = low_bit[w->v8[0]];
    783   if (value != -1)
    784     return value;
    785   value = low_bit[w->v8[1]];
    786   if (value != -1)
    787     return value + 8;
    788   value = low_bit[w->v8[2]];
    789   if (value != -1)
    790     return value + 16;
    791   value = low_bit[w->v8[3]];
    792   if (value == -1)
    793     return -1;
    794   return value + 24;
    795 }
    796 
    797 /* high_bit not done yet */
    798 
    799 
    800 
    801 
    802 
    803