type-id.c++ (13649B)
1 // Copyright (c) 2013-2017 Sandstorm Development Group, Inc. and contributors 2 // Licensed under the MIT License: 3 // 4 // Permission is hereby granted, free of charge, to any person obtaining a copy 5 // of this software and associated documentation files (the "Software"), to deal 6 // in the Software without restriction, including without limitation the rights 7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 8 // copies of the Software, and to permit persons to whom the Software is 9 // furnished to do so, subject to the following conditions: 10 // 11 // The above copyright notice and this permission notice shall be included in 12 // all copies or substantial portions of the Software. 13 // 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 20 // THE SOFTWARE. 21 22 #include "type-id.h" 23 #include <kj/debug.h> 24 #include <string.h> 25 26 namespace capnp { 27 namespace compiler { 28 29 class TypeIdGenerator { 30 // A non-cryptographic deterministic random number generator used to generate type IDs when the 31 // developer did not specify one themselves. 32 // 33 // The underlying algorithm is MD5. MD5 is safe to use here because this is not intended to be a 34 // cryptographic random number generator. In retrospect it would have been nice to use something 35 // else just to avoid people freaking out about it, but changing the algorithm now would break 36 // backwards-compatibility. 37 38 public: 39 TypeIdGenerator(); 40 41 void update(kj::ArrayPtr<const kj::byte> data); 42 inline void update(kj::ArrayPtr<const char> data) { 43 return update(data.asBytes()); 44 } 45 inline void update(kj::StringPtr data) { 46 return update(data.asArray()); 47 } 48 49 kj::ArrayPtr<const kj::byte> finish(); 50 51 private: 52 bool finished = false; 53 54 struct { 55 uint lo, hi; 56 uint a, b, c, d; 57 kj::byte buffer[64]; 58 uint block[16]; 59 } ctx; 60 61 const kj::byte* body(const kj::byte* ptr, size_t size); 62 }; 63 64 uint64_t generateChildId(uint64_t parentId, kj::StringPtr childName) { 65 // Compute ID by hashing the concatenation of the parent ID and the declaration name, and 66 // then taking the first 8 bytes. 67 68 kj::byte parentIdBytes[sizeof(uint64_t)]; 69 for (uint i = 0; i < sizeof(uint64_t); i++) { 70 parentIdBytes[i] = (parentId >> (i * 8)) & 0xff; 71 } 72 73 TypeIdGenerator generator; 74 generator.update(kj::arrayPtr(parentIdBytes, kj::size(parentIdBytes))); 75 generator.update(childName); 76 77 kj::ArrayPtr<const kj::byte> resultBytes = generator.finish(); 78 79 uint64_t result = 0; 80 for (uint i = 0; i < sizeof(uint64_t); i++) { 81 result = (result << 8) | resultBytes[i]; 82 } 83 84 return result | (1ull << 63); 85 } 86 87 uint64_t generateGroupId(uint64_t parentId, uint16_t groupIndex) { 88 // Compute ID by hashing the concatenation of the parent ID and the group index, and 89 // then taking the first 8 bytes. 90 91 kj::byte bytes[sizeof(uint64_t) + sizeof(uint16_t)]; 92 for (uint i = 0; i < sizeof(uint64_t); i++) { 93 bytes[i] = (parentId >> (i * 8)) & 0xff; 94 } 95 for (uint i = 0; i < sizeof(uint16_t); i++) { 96 bytes[sizeof(uint64_t) + i] = (groupIndex >> (i * 8)) & 0xff; 97 } 98 99 TypeIdGenerator generator; 100 generator.update(bytes); 101 102 kj::ArrayPtr<const kj::byte> resultBytes = generator.finish(); 103 104 uint64_t result = 0; 105 for (uint i = 0; i < sizeof(uint64_t); i++) { 106 result = (result << 8) | resultBytes[i]; 107 } 108 109 return result | (1ull << 63); 110 } 111 112 uint64_t generateMethodParamsId(uint64_t parentId, uint16_t methodOrdinal, bool isResults) { 113 // Compute ID by hashing the concatenation of the parent ID, the method ordinal, and a 114 // boolean indicating whether this is the params or the results, and then taking the first 8 115 // bytes. 116 117 kj::byte bytes[sizeof(uint64_t) + sizeof(uint16_t) + 1]; 118 for (uint i = 0; i < sizeof(uint64_t); i++) { 119 bytes[i] = (parentId >> (i * 8)) & 0xff; 120 } 121 for (uint i = 0; i < sizeof(uint16_t); i++) { 122 bytes[sizeof(uint64_t) + i] = (methodOrdinal >> (i * 8)) & 0xff; 123 } 124 bytes[sizeof(bytes) - 1] = isResults; 125 126 TypeIdGenerator generator; 127 generator.update(bytes); 128 129 kj::ArrayPtr<const kj::byte> resultBytes = generator.finish(); 130 131 uint64_t result = 0; 132 for (uint i = 0; i < sizeof(uint64_t); i++) { 133 result = (result << 8) | resultBytes[i]; 134 } 135 136 return result | (1ull << 63); 137 } 138 139 // The remainder of this file was derived from code placed in the public domain. 140 // The original code bore the following notice: 141 142 /* 143 * This is an OpenSSL-compatible implementation of the RSA Data Security, Inc. 144 * MD5 Message-Digest Algorithm (RFC 1321). 145 * 146 * Homepage: 147 * http://openwall.info/wiki/people/solar/software/public-domain-source-code/md5 148 * 149 * Author: 150 * Alexander Peslyak, better known as Solar Designer <solar at openwall.com> 151 * 152 * This software was written by Alexander Peslyak in 2001. No copyright is 153 * claimed, and the software is hereby placed in the public domain. 154 * In case this attempt to disclaim copyright and place the software in the 155 * public domain is deemed null and void, then the software is 156 * Copyright (c) 2001 Alexander Peslyak and it is hereby released to the 157 * general public under the following terms: 158 * 159 * Redistribution and use in source and binary forms, with or without 160 * modification, are permitted. 161 * 162 * There's ABSOLUTELY NO WARRANTY, express or implied. 163 * 164 * (This is a heavily cut-down "BSD license".) 165 * 166 * This differs from Colin Plumb's older public domain implementation in that 167 * no exactly 32-bit integer data type is required (any 32-bit or wider 168 * unsigned integer data type will do), there's no compile-time endianness 169 * configuration, and the function prototypes match OpenSSL's. No code from 170 * Colin Plumb's implementation has been reused; this comment merely compares 171 * the properties of the two independent implementations. 172 * 173 * The primary goals of this implementation are portability and ease of use. 174 * It is meant to be fast, but not as fast as possible. Some known 175 * optimizations are not included to reduce source code size and avoid 176 * compile-time configuration. 177 */ 178 179 /* 180 * The basic MD5 functions. 181 * 182 * F and G are optimized compared to their RFC 1321 definitions for 183 * architectures that lack an AND-NOT instruction, just like in Colin Plumb's 184 * implementation. 185 */ 186 #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) 187 #define G(x, y, z) ((y) ^ ((z) & ((x) ^ (y)))) 188 #define H(x, y, z) ((x) ^ (y) ^ (z)) 189 #define I(x, y, z) ((y) ^ ((x) | ~(z))) 190 191 /* 192 * The MD5 transformation for all four rounds. 193 */ 194 #define STEP(f, a, b, c, d, x, t, s) \ 195 (a) += f((b), (c), (d)) + (x) + (t); \ 196 (a) = (((a) << (s)) | (((a) & 0xffffffff) >> (32 - (s)))); \ 197 (a) += (b); 198 199 /* 200 * SET reads 4 input bytes in little-endian byte order and stores them 201 * in a properly aligned word in host byte order. 202 * 203 * The check for little-endian architectures that tolerate unaligned 204 * memory accesses is just an optimization. Nothing will break if it 205 * doesn't work. 206 */ 207 #if defined(__i386__) || defined(__x86_64__) || defined(__vax__) 208 #define SET(n) \ 209 (*(uint *)&ptr[(n) * 4]) 210 #define GET(n) \ 211 SET(n) 212 #else 213 #define SET(n) \ 214 (ctx.block[(n)] = \ 215 (uint)ptr[(n) * 4] | \ 216 ((uint)ptr[(n) * 4 + 1] << 8) | \ 217 ((uint)ptr[(n) * 4 + 2] << 16) | \ 218 ((uint)ptr[(n) * 4 + 3] << 24)) 219 #define GET(n) \ 220 (ctx.block[(n)]) 221 #endif 222 223 /* 224 * This processes one or more 64-byte data blocks, but does NOT update 225 * the bit counters. There are no alignment requirements. 226 */ 227 const kj::byte* TypeIdGenerator::body(const kj::byte* ptr, size_t size) 228 { 229 uint a, b, c, d; 230 uint saved_a, saved_b, saved_c, saved_d; 231 232 a = ctx.a; 233 b = ctx.b; 234 c = ctx.c; 235 d = ctx.d; 236 237 do { 238 saved_a = a; 239 saved_b = b; 240 saved_c = c; 241 saved_d = d; 242 243 /* Round 1 */ 244 STEP(F, a, b, c, d, SET(0), 0xd76aa478, 7) 245 STEP(F, d, a, b, c, SET(1), 0xe8c7b756, 12) 246 STEP(F, c, d, a, b, SET(2), 0x242070db, 17) 247 STEP(F, b, c, d, a, SET(3), 0xc1bdceee, 22) 248 STEP(F, a, b, c, d, SET(4), 0xf57c0faf, 7) 249 STEP(F, d, a, b, c, SET(5), 0x4787c62a, 12) 250 STEP(F, c, d, a, b, SET(6), 0xa8304613, 17) 251 STEP(F, b, c, d, a, SET(7), 0xfd469501, 22) 252 STEP(F, a, b, c, d, SET(8), 0x698098d8, 7) 253 STEP(F, d, a, b, c, SET(9), 0x8b44f7af, 12) 254 STEP(F, c, d, a, b, SET(10), 0xffff5bb1, 17) 255 STEP(F, b, c, d, a, SET(11), 0x895cd7be, 22) 256 STEP(F, a, b, c, d, SET(12), 0x6b901122, 7) 257 STEP(F, d, a, b, c, SET(13), 0xfd987193, 12) 258 STEP(F, c, d, a, b, SET(14), 0xa679438e, 17) 259 STEP(F, b, c, d, a, SET(15), 0x49b40821, 22) 260 261 /* Round 2 */ 262 STEP(G, a, b, c, d, GET(1), 0xf61e2562, 5) 263 STEP(G, d, a, b, c, GET(6), 0xc040b340, 9) 264 STEP(G, c, d, a, b, GET(11), 0x265e5a51, 14) 265 STEP(G, b, c, d, a, GET(0), 0xe9b6c7aa, 20) 266 STEP(G, a, b, c, d, GET(5), 0xd62f105d, 5) 267 STEP(G, d, a, b, c, GET(10), 0x02441453, 9) 268 STEP(G, c, d, a, b, GET(15), 0xd8a1e681, 14) 269 STEP(G, b, c, d, a, GET(4), 0xe7d3fbc8, 20) 270 STEP(G, a, b, c, d, GET(9), 0x21e1cde6, 5) 271 STEP(G, d, a, b, c, GET(14), 0xc33707d6, 9) 272 STEP(G, c, d, a, b, GET(3), 0xf4d50d87, 14) 273 STEP(G, b, c, d, a, GET(8), 0x455a14ed, 20) 274 STEP(G, a, b, c, d, GET(13), 0xa9e3e905, 5) 275 STEP(G, d, a, b, c, GET(2), 0xfcefa3f8, 9) 276 STEP(G, c, d, a, b, GET(7), 0x676f02d9, 14) 277 STEP(G, b, c, d, a, GET(12), 0x8d2a4c8a, 20) 278 279 /* Round 3 */ 280 STEP(H, a, b, c, d, GET(5), 0xfffa3942, 4) 281 STEP(H, d, a, b, c, GET(8), 0x8771f681, 11) 282 STEP(H, c, d, a, b, GET(11), 0x6d9d6122, 16) 283 STEP(H, b, c, d, a, GET(14), 0xfde5380c, 23) 284 STEP(H, a, b, c, d, GET(1), 0xa4beea44, 4) 285 STEP(H, d, a, b, c, GET(4), 0x4bdecfa9, 11) 286 STEP(H, c, d, a, b, GET(7), 0xf6bb4b60, 16) 287 STEP(H, b, c, d, a, GET(10), 0xbebfbc70, 23) 288 STEP(H, a, b, c, d, GET(13), 0x289b7ec6, 4) 289 STEP(H, d, a, b, c, GET(0), 0xeaa127fa, 11) 290 STEP(H, c, d, a, b, GET(3), 0xd4ef3085, 16) 291 STEP(H, b, c, d, a, GET(6), 0x04881d05, 23) 292 STEP(H, a, b, c, d, GET(9), 0xd9d4d039, 4) 293 STEP(H, d, a, b, c, GET(12), 0xe6db99e5, 11) 294 STEP(H, c, d, a, b, GET(15), 0x1fa27cf8, 16) 295 STEP(H, b, c, d, a, GET(2), 0xc4ac5665, 23) 296 297 /* Round 4 */ 298 STEP(I, a, b, c, d, GET(0), 0xf4292244, 6) 299 STEP(I, d, a, b, c, GET(7), 0x432aff97, 10) 300 STEP(I, c, d, a, b, GET(14), 0xab9423a7, 15) 301 STEP(I, b, c, d, a, GET(5), 0xfc93a039, 21) 302 STEP(I, a, b, c, d, GET(12), 0x655b59c3, 6) 303 STEP(I, d, a, b, c, GET(3), 0x8f0ccc92, 10) 304 STEP(I, c, d, a, b, GET(10), 0xffeff47d, 15) 305 STEP(I, b, c, d, a, GET(1), 0x85845dd1, 21) 306 STEP(I, a, b, c, d, GET(8), 0x6fa87e4f, 6) 307 STEP(I, d, a, b, c, GET(15), 0xfe2ce6e0, 10) 308 STEP(I, c, d, a, b, GET(6), 0xa3014314, 15) 309 STEP(I, b, c, d, a, GET(13), 0x4e0811a1, 21) 310 STEP(I, a, b, c, d, GET(4), 0xf7537e82, 6) 311 STEP(I, d, a, b, c, GET(11), 0xbd3af235, 10) 312 STEP(I, c, d, a, b, GET(2), 0x2ad7d2bb, 15) 313 STEP(I, b, c, d, a, GET(9), 0xeb86d391, 21) 314 315 a += saved_a; 316 b += saved_b; 317 c += saved_c; 318 d += saved_d; 319 320 ptr += 64; 321 } while (size -= 64); 322 323 ctx.a = a; 324 ctx.b = b; 325 ctx.c = c; 326 ctx.d = d; 327 328 return ptr; 329 } 330 331 TypeIdGenerator::TypeIdGenerator() 332 { 333 ctx.a = 0x67452301; 334 ctx.b = 0xefcdab89; 335 ctx.c = 0x98badcfe; 336 ctx.d = 0x10325476; 337 338 ctx.lo = 0; 339 ctx.hi = 0; 340 } 341 342 void TypeIdGenerator::update(kj::ArrayPtr<const kj::byte> dataArray) 343 { 344 KJ_REQUIRE(!finished, "already called TypeIdGenerator::finish()"); 345 346 const kj::byte* data = dataArray.begin(); 347 unsigned long size = dataArray.size(); 348 349 uint saved_lo; 350 unsigned long used, free; 351 352 saved_lo = ctx.lo; 353 if ((ctx.lo = (saved_lo + size) & 0x1fffffff) < saved_lo) 354 ctx.hi++; 355 ctx.hi += size >> 29; 356 357 used = saved_lo & 0x3f; 358 359 if (used) { 360 free = 64 - used; 361 362 if (size < free) { 363 memcpy(&ctx.buffer[used], data, size); 364 return; 365 } 366 367 memcpy(&ctx.buffer[used], data, free); 368 data = data + free; 369 size -= free; 370 body(ctx.buffer, 64); 371 } 372 373 if (size >= 64) { 374 data = body(data, size & ~(unsigned long)0x3f); 375 size &= 0x3f; 376 } 377 378 memcpy(ctx.buffer, data, size); 379 } 380 381 kj::ArrayPtr<const kj::byte> TypeIdGenerator::finish() 382 { 383 if (!finished) { 384 unsigned long used, free; 385 386 used = ctx.lo & 0x3f; 387 388 ctx.buffer[used++] = 0x80; 389 390 free = 64 - used; 391 392 if (free < 8) { 393 memset(&ctx.buffer[used], 0, free); 394 body(ctx.buffer, 64); 395 used = 0; 396 free = 64; 397 } 398 399 memset(&ctx.buffer[used], 0, free - 8); 400 401 ctx.lo <<= 3; 402 ctx.buffer[56] = ctx.lo; 403 ctx.buffer[57] = ctx.lo >> 8; 404 ctx.buffer[58] = ctx.lo >> 16; 405 ctx.buffer[59] = ctx.lo >> 24; 406 ctx.buffer[60] = ctx.hi; 407 ctx.buffer[61] = ctx.hi >> 8; 408 ctx.buffer[62] = ctx.hi >> 16; 409 ctx.buffer[63] = ctx.hi >> 24; 410 411 body(ctx.buffer, 64); 412 413 // Store final result into ctx.buffer. 414 ctx.buffer[0] = ctx.a; 415 ctx.buffer[1] = ctx.a >> 8; 416 ctx.buffer[2] = ctx.a >> 16; 417 ctx.buffer[3] = ctx.a >> 24; 418 ctx.buffer[4] = ctx.b; 419 ctx.buffer[5] = ctx.b >> 8; 420 ctx.buffer[6] = ctx.b >> 16; 421 ctx.buffer[7] = ctx.b >> 24; 422 ctx.buffer[8] = ctx.c; 423 ctx.buffer[9] = ctx.c >> 8; 424 ctx.buffer[10] = ctx.c >> 16; 425 ctx.buffer[11] = ctx.c >> 24; 426 ctx.buffer[12] = ctx.d; 427 ctx.buffer[13] = ctx.d >> 8; 428 ctx.buffer[14] = ctx.d >> 16; 429 ctx.buffer[15] = ctx.d >> 24; 430 431 finished = true; 432 } 433 434 return kj::arrayPtr(ctx.buffer, 16); 435 } 436 437 438 } // namespace compiler 439 } // namespace capnp