Alexandre Lision | 51140e1 | 2013-12-02 10:54:09 -0500 | [diff] [blame] | 1 | /** |
| 2 | * |
| 3 | * Copyright (c) 2002 Bryce "Zooko" Wilcox-O'Hearn Permission is hereby |
| 4 | * granted, free of charge, to any person obtaining a copy of this software to |
| 5 | * deal in this software without restriction, including without limitation the |
| 6 | * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or |
| 7 | * sell copies of this software, and to permit persons to whom this software |
| 8 | * is furnished to do so, subject to the following conditions: |
| 9 | * |
| 10 | * The above copyright notice and this permission notice shall be included in |
| 11 | * all copies or substantial portions of this software. |
| 12 | * |
| 13 | * THIS SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 14 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 15 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| 16 | * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| 17 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| 18 | * FROM, OUT OF OR IN CONNECTION WITH THIS SOFTWARE OR THE USE OR OTHER |
| 19 | * DEALINGS IN THIS SOFTWARE. |
| 20 | * |
| 21 | * Converted to C++ by: |
| 22 | * @author Werner Dittmann <Werner.Dittmann@t-online.de> |
| 23 | */ |
| 24 | #ifndef UNIT_TEST |
| 25 | #include <libzrtpcpp/Base32.h> |
| 26 | #else |
| 27 | #include "libzrtpcpp/Base32.h" |
| 28 | #endif |
| 29 | |
| 30 | int divceil(int a, int b) { |
| 31 | int c; |
| 32 | if (a>0) { |
| 33 | if (b>0) c=a+b-1; |
| 34 | else c=a; |
| 35 | } else { |
| 36 | if (b>0) c=a; |
| 37 | else c=a+b+1; |
| 38 | } |
| 39 | return c/b; |
| 40 | } |
| 41 | |
| 42 | // 1 2 3 |
| 43 | // 01234567890123456789012345678901 |
| 44 | static const char* const chars= "ybndrfg8ejkmcpqxot1uwisza345h769"; |
| 45 | |
| 46 | /* |
| 47 | * revchars: index into this table with the ASCII value of the char. |
| 48 | * The result is the value of that quintet. |
| 49 | */ |
| 50 | static const unsigned char revchars[]= { |
| 51 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 52 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 53 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 54 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 55 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 56 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 57 | 255, 18, 255, 25, 26, 27, 30, 29, |
| 58 | 7, 31, 255, 255, 255, 255, 255, 255, |
| 59 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 60 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 61 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 62 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 63 | 255, 24, 1, 12, 3, 8, 5, 6, |
| 64 | 28, 21, 9, 10, 255, 11, 2, 16, |
| 65 | 13, 14, 4, 22, 17, 19, 255, 20, |
| 66 | 15, 0, 23, 255, 255, 255, 255, 255, |
| 67 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 68 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 69 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 70 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 71 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 72 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 73 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 74 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 75 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 76 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 77 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 78 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 79 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 80 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 81 | 255, 255, 255, 255, 255, 255, 255, 255, |
| 82 | 255, 255, 255, 255, 255, 255, 255, 255 |
| 83 | }; |
| 84 | |
| 85 | |
| 86 | Base32::Base32(const string encoded): |
| 87 | binaryResult(NULL), resultLength(0) { |
| 88 | |
| 89 | a2b_l(encoded, encoded.size(), (encoded.size()*5/8)*8); |
| 90 | } |
| 91 | |
| 92 | Base32::Base32(const string encoded, int noOfBits): |
| 93 | binaryResult(NULL), resultLength(0) { |
| 94 | |
| 95 | a2b_l(encoded, divceil(noOfBits, 5), noOfBits); |
| 96 | } |
| 97 | |
| 98 | Base32::Base32(const unsigned char* data, int noOfBits): |
| 99 | binaryResult(NULL), resultLength(0) { |
| 100 | |
| 101 | b2a_l(data, (noOfBits+7)/8, noOfBits); |
| 102 | } |
| 103 | |
| 104 | Base32::~Base32() { |
| 105 | if (binaryResult != NULL && binaryResult != smallBuffer) { |
| 106 | delete [] binaryResult; |
| 107 | } |
| 108 | binaryResult = NULL; |
| 109 | } |
| 110 | |
| 111 | const unsigned char* Base32::getDecoded(int &length) { |
| 112 | length = resultLength; |
| 113 | return binaryResult; |
| 114 | } |
| 115 | |
| 116 | void Base32::b2a_l(const unsigned char* os, int len, |
| 117 | const size_t lengthinbits) { |
| 118 | |
| 119 | /* if lengthinbits is not a multiple of 8 then this is allocating |
| 120 | * space for 0, 1, or 2 extra quintets that will be truncated at the |
| 121 | * end of this function if they are not needed |
| 122 | */ |
| 123 | string result(divceil(len*8, 5), ' '); |
| 124 | |
| 125 | /* index into the result buffer, initially pointing to the |
| 126 | * "one-past-the-end" quintet |
| 127 | */ |
| 128 | int resp = result.size(); |
| 129 | |
| 130 | /* pointer into the os buffer, initially pointing to the |
| 131 | * "one-past-the-end" octet |
| 132 | */ |
| 133 | const unsigned char* osp = os + len; |
| 134 | |
| 135 | /* Now this is a real live Duff's device. You gotta love it. */ |
| 136 | |
| 137 | unsigned long x = 0; // to hold up to 32 bits worth of the input |
| 138 | switch ((osp - os) % 5) { |
| 139 | |
| 140 | case 0: |
| 141 | do { |
| 142 | x = *--osp; |
| 143 | result[--resp] = chars[x % 32]; /* The least sig 5 bits go into the final quintet. */ |
| 144 | x /= 32; /* ... now we have 3 bits worth in x... */ |
| 145 | case 4: |
| 146 | x |= ((unsigned long)(*--osp)) << 3; /* ... now we have 11 bits worth in x... */ |
| 147 | result[--resp] = chars[x % 32]; |
| 148 | x /= 32; /* ... now we have 6 bits worth in x... */ |
| 149 | result[--resp] = chars[x % 32]; |
| 150 | x /= 32; /* ... now we have 1 bits worth in x... */ |
| 151 | case 3: |
| 152 | x |= ((unsigned long)(*--osp)) << 1; /* The 8 bits from the 2-indexed octet. |
| 153 | So now we have 9 bits worth in x... */ |
| 154 | result[--resp] = chars[x % 32]; |
| 155 | x /= 32; /* ... now we have 4 bits worth in x... */ |
| 156 | case 2: |
| 157 | x |= ((unsigned long)(*--osp)) << 4; /* The 8 bits from the 1-indexed octet. |
| 158 | So now we have 12 bits worth in x... */ |
| 159 | result[--resp] = chars[x%32]; |
| 160 | x /= 32; /* ... now we have 7 bits worth in x... */ |
| 161 | result[--resp] = chars[x%32]; |
| 162 | x /= 32; /* ... now we have 2 bits worth in x... */ |
| 163 | case 1: |
| 164 | x |= ((unsigned long)(*--osp)) << 2; /* The 8 bits from the 0-indexed octet. |
| 165 | So now we have 10 bits worth in x... */ |
| 166 | result[--resp] = chars[x%32]; |
| 167 | x /= 32; /* ... now we have 5 bits worth in x... */ |
| 168 | result[--resp] = chars[x]; |
| 169 | } while (osp > os); |
| 170 | } /* switch ((osp - os.buf) % 5) */ |
| 171 | |
| 172 | /* truncate any unused trailing zero quintets */ |
| 173 | encoded = result.substr(0, divceil(lengthinbits, 5)); |
| 174 | return; |
| 175 | } |
| 176 | |
| 177 | void Base32::a2b_l(const string cs, size_t size, const size_t lengthinbits ) { |
| 178 | unsigned long x = 0; // to hold up to 32 bits worth of the input |
| 179 | |
| 180 | int len = divceil(size*5, 8); |
| 181 | |
| 182 | /* if lengthinbits is not a multiple of 5 then this is |
| 183 | * allocating space for 0 or 1 extra octets that will be |
| 184 | * truncated at the end of this function if they are |
| 185 | * not needed |
| 186 | */ |
| 187 | |
| 188 | if (len < 128) { |
| 189 | binaryResult = smallBuffer; |
| 190 | } |
| 191 | else { |
| 192 | binaryResult = new unsigned char[len]; |
| 193 | } |
| 194 | |
| 195 | /* pointer into the result buffer, initially pointing to |
| 196 | * the "one-past-the-end" octet |
| 197 | */ |
| 198 | unsigned char* resp = binaryResult + len; |
| 199 | |
| 200 | /* index into the input buffer, initially pointing to the |
| 201 | * "one-past-the-end" character |
| 202 | */ |
| 203 | int csp = size; |
| 204 | |
| 205 | /* Now this is a real live Duff's device. You gotta love it. */ |
| 206 | switch (csp % 8) { |
| 207 | case 0: |
| 208 | do { |
| 209 | x = revchars[cs[--csp]&0xff]; /* 5 bits... */ |
| 210 | case 7: |
| 211 | x |= revchars[cs[--csp]&0xff] << 5; /* 10 bits... */ |
| 212 | *--resp = x % 256; |
| 213 | x /= 256; /* 2 bits... */ |
| 214 | case 6: |
| 215 | x |= revchars[cs[--csp]&0xff] << 2; /* 7 bits... */ |
| 216 | case 5: |
| 217 | x |= revchars[cs[--csp]&0xff] << 7; /* 12 bits... */ |
| 218 | *--resp = x % 256; |
| 219 | x /= 256; /* 4 bits... */ |
| 220 | case 4: |
| 221 | x |= revchars[cs[--csp]&0xff] << 4; /* 9 bits... */ |
| 222 | *--resp = x % 256; |
| 223 | x /= 256; /* 1 bit... */ |
| 224 | case 3: |
| 225 | x |= revchars[cs[--csp]&0xff] << 1; /* 6 bits... */ |
| 226 | case 2: |
| 227 | x |= revchars[cs[--csp]&0xff] << 6; /* 11 bits... */ |
| 228 | *--resp = x % 256; |
| 229 | x /= 256; /* 3 bits... */ |
| 230 | case 1: |
| 231 | x |= revchars[cs[--csp]&0xff] << 3; /* 8 bits... */ |
| 232 | *--resp = x % 256; |
| 233 | } while (csp); |
| 234 | } /* switch ((csp - cs.buf) % 8) */ |
| 235 | |
| 236 | /* truncate any unused trailing zero octets */ |
| 237 | resultLength = divceil(lengthinbits, 8); |
| 238 | return; |
| 239 | } |
| 240 | |
| 241 | #ifdef UNIT_TEST |
| 242 | #include <math.h> |
| 243 | |
| 244 | |
| 245 | static uint8_t *randz(const size_t len) |
| 246 | { |
| 247 | uint8_t* result = (uint8_t*)malloc(len); |
| 248 | size_t i; |
| 249 | for (i=0; i<len; i++) { |
| 250 | result[i] = rand() % 256; |
| 251 | } |
| 252 | return result; |
| 253 | } |
| 254 | |
| 255 | int main(int argc, char *argv[]) { |
| 256 | |
| 257 | int32_t resLen; |
| 258 | string a; |
| 259 | const uint8_t* zrecovered; |
| 260 | uint8_t ones[] = {1, 1, 1, 1, 1}; |
| 261 | uint8_t zrtpVec01[] = {0x00, 0x00, 0x00, 0x00}; |
| 262 | uint8_t zrtpVec02[] = {0x80, 0x00, 0x00, 0x00}; |
| 263 | uint8_t zrtpVec03[] = {0x40, 0x00, 0x00, 0x00}; |
| 264 | uint8_t zrtpVec04[] = {0xc0, 0x00, 0x00, 0x00}; |
| 265 | uint8_t zrtpVec05[] = {0x00, 0x00, 0x00, 0x00}; |
| 266 | uint8_t zrtpVec06[] = {0x80, 0x80, 0x00, 0x00}; |
| 267 | uint8_t zrtpVec07[] = {0x8b, 0x88, 0x80, 0x00}; |
| 268 | uint8_t zrtpVec08[] = {0xf0, 0xbf, 0xc7, 0x00}; |
| 269 | uint8_t zrtpVec09[] = {0xd4, 0x7a, 0x04, 0x00}; |
| 270 | uint8_t zrtpVec10[] = {0xf5, 0x57, 0xbb, 0x0c}; |
| 271 | |
| 272 | // Encode all bits of the 5 one bytes (= 40 bits) |
| 273 | a = Base32(ones, 5*8).getEncoded(); |
| 274 | |
| 275 | // The string should be: "yryonyeb" |
| 276 | cout << "Encoded 5 ones: '" << a << "', Expected: 'yryonyeb'" << endl; |
| 277 | |
| 278 | // Now decode all bits and check |
| 279 | Base32 *y = new Base32(a); |
| 280 | zrecovered = y->getDecoded(resLen); |
| 281 | if (resLen != 5 && memcmp(ones, zrecovered, 5)) { |
| 282 | printf("Failed basic 5 ones recovery test.\n"); |
| 283 | return -1; |
| 284 | } |
| 285 | delete y; |
| 286 | |
| 287 | a = Base32(ones, 15).getEncoded(); |
| 288 | cout << "Encoded 5 ones, 15 bits only: '" << a << "', Expected: 'yry'" << endl; |
| 289 | // now decode 15 bits (out of 40 possible) |
| 290 | y = new Base32(a, 15); |
| 291 | zrecovered = y->getDecoded(resLen); |
| 292 | printf("Decoded 15 bits, result length: %d (should be 2)\n", resLen); |
| 293 | printf("Decoded bytes: %x %x (should be 1 0)\n", zrecovered[0], zrecovered[1]); |
| 294 | delete y; |
| 295 | |
| 296 | // Encode 20 bits of the test vectors |
| 297 | a = Base32(zrtpVec01, 20).getEncoded(); |
| 298 | cout << "Encoded ZRTP vector 01: '" << a << "', Expected: 'yyyy'" << endl; |
| 299 | a = Base32(zrtpVec02, 20).getEncoded(); |
| 300 | cout << "Encoded ZRTP vector 02: '" << a << "', Expected: 'oyyy'" << endl; |
| 301 | a = Base32(zrtpVec03, 20).getEncoded(); |
| 302 | cout << "Encoded ZRTP vector 02: '" << a << "', Expected: 'eyyy'" << endl; |
| 303 | a = Base32(zrtpVec04, 20).getEncoded(); |
| 304 | cout << "Encoded ZRTP vector 04: '" << a << "', Expected: 'ayyy'" << endl; |
| 305 | a = Base32(zrtpVec05, 20).getEncoded(); |
| 306 | cout << "Encoded ZRTP vector 05: '" << a << "', Expected: 'yyyy'" << endl; |
| 307 | a = Base32(zrtpVec06, 20).getEncoded(); |
| 308 | cout << "Encoded ZRTP vector 06: '" << a << "', Expected: 'onyy'" << endl; |
| 309 | a = Base32(zrtpVec07, 20).getEncoded(); |
| 310 | cout << "Encoded ZRTP vector 07: '" << a << "', Expected: 'tqre'" << endl; |
| 311 | a = Base32(zrtpVec08, 20).getEncoded(); |
| 312 | cout << "Encoded ZRTP vector 08: '" << a << "', Expected: '6n9h'" << endl; |
| 313 | a = Base32(zrtpVec09, 20).getEncoded(); |
| 314 | cout << "Encoded ZRTP vector 09: '" << a << "', Expected: '4t7y'" << endl; |
| 315 | a = Base32(zrtpVec10, 20).getEncoded(); |
| 316 | cout << "Encoded ZRTP vector 10: '" << a << "', Expected: '6im5'" << endl; |
| 317 | |
| 318 | // test the 30 bit output of same data as 20 bit |
| 319 | a = Base32(zrtpVec10, 30).getEncoded(); |
| 320 | cout << "Encoded ZRTP vector 10 (30bit): '" << a << "', Expected: '6im5sd'" << endl; |
| 321 | |
| 322 | for (int i = 0; i < 2; i++) { |
| 323 | uint8_t* z = randz(16); |
| 324 | a = Base32(z, 16*8).getEncoded(); |
| 325 | // cout << "Result: " << a << endl; |
| 326 | assert (a.size() == Base32::b2alen(16*8)); |
| 327 | zrecovered = Base32(a).getDecoded(resLen); |
| 328 | if (resLen != 16 && memcmp(z, zrecovered, 16)) { |
| 329 | printf("Failed basic recovery test.\n"); |
| 330 | return -1; |
| 331 | } |
| 332 | free((void*)z); |
| 333 | } |
| 334 | } |
| 335 | #endif |