diff options
Diffstat (limited to 'cicn-plugin/cicn/cicn_siphash.h')
| -rw-r--r-- | cicn-plugin/cicn/cicn_siphash.h | 458 |
1 files changed, 458 insertions, 0 deletions
diff --git a/cicn-plugin/cicn/cicn_siphash.h b/cicn-plugin/cicn/cicn_siphash.h new file mode 100644 index 00000000..9b537828 --- /dev/null +++ b/cicn-plugin/cicn/cicn_siphash.h @@ -0,0 +1,458 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/* + SipHash reference C implementation + + Copyright (c) 2012-2014 Jean-Philippe Aumasson + <jeanphilippe.aumasson@gmail.com> + Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to> + + To the extent possible under law, the author(s) have dedicated all copyright + and related and neighboring rights to this software to the public domain + worldwide. This software is distributed without any warranty. + + You should have received a copy of the CC0 Public Domain Dedication along + with + this software. If not, see + <http://creativecommons.org/publicdomain/zero/1.0/>. + */ +#ifndef _CICN_SIPHASH_H_ +#define _CICN_SIPHASH_H_ 1 + +#if !CICN_VPP_PLUGIN +#error "cicn-internal file included externally" +#endif + +#include <stdint.h> +#include <stdio.h> +#include <string.h> + +/* default: SipHash-2-4 */ +#define cROUNDS 2 +#define dROUNDS 4 + +#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) + +#define U32TO8_LE(p, v) \ + (p)[0] = (uint8_t)((v)); \ + (p)[1] = (uint8_t)((v) >> 8); \ + (p)[2] = (uint8_t)((v) >> 16); \ + (p)[3] = (uint8_t)((v) >> 24); + +#define U64TO8_LE(p, v) \ + U32TO8_LE((p), (uint32_t)((v))); \ + U32TO8_LE((p) + 4, (uint32_t)((v) >> 32)); + +#define U8TO64_LE(p) \ + (((uint64_t)((p)[0])) | ((uint64_t)((p)[1]) << 8) | \ + ((uint64_t)((p)[2]) << 16) | ((uint64_t)((p)[3]) << 24) | \ + ((uint64_t)((p)[4]) << 32) | ((uint64_t)((p)[5]) << 40) | \ + ((uint64_t)((p)[6]) << 48) | ((uint64_t)((p)[7]) << 56)) + +#define SIPROUND \ + do { \ + v0 += v1; \ + v1 = ROTL(v1, 13); \ + v1 ^= v0; \ + v0 = ROTL(v0, 32); \ + v2 += v3; \ + v3 = ROTL(v3, 16); \ + v3 ^= v2; \ + v0 += v3; \ + v3 = ROTL(v3, 21); \ + v3 ^= v0; \ + v2 += v1; \ + v1 = ROTL(v1, 17); \ + v1 ^= v2; \ + v2 = ROTL(v2, 32); \ + } while (0) + +#ifdef CICN_SIPHASH_DEBUG +#define SIPTRACE \ + do { \ + printf("(%3d) v0 %08x %08x\n", (int)inlen, (uint32_t)(v0 >> 32), \ + (uint32_t)v0); \ + printf("(%3d) v1 %08x %08x\n", (int)inlen, (uint32_t)(v1 >> 32), \ + (uint32_t)v1); \ + printf("(%3d) v2 %08x %08x\n", (int)inlen, (uint32_t)(v2 >> 32), \ + (uint32_t)v2); \ + printf("(%3d) v3 %08x %08x\n", (int)inlen, (uint32_t)(v3 >> 32), \ + (uint32_t)v3); \ + } while (0) +#else +#define SIPTRACE +#endif + +#ifdef CICN_SIPHASH_128 // exp. 128-bit code below, ifdef'd out, for reference +#error "cicn_siphash doesn't support 128-bit yet!" +#endif + +/* Cool - need an extern declaration in order to keep llvm happy... */ +extern inline uint64_t +cicn_siphash (const uint8_t * in, uint64_t inlen, const uint8_t * k); + +/* + * + */ +inline uint64_t +cicn_siphash (const uint8_t * in, uint64_t inlen, const uint8_t * k) +{ + /* "somepseudorandomlygeneratedbytes" */ + uint64_t v0 = 0x736f6d6570736575ULL; + uint64_t v1 = 0x646f72616e646f6dULL; + uint64_t v2 = 0x6c7967656e657261ULL; + uint64_t v3 = 0x7465646279746573ULL; + uint64_t b; + uint64_t k0 = U8TO64_LE (k); + uint64_t k1 = U8TO64_LE (k + 8); + uint64_t m; + int i; + const uint8_t *end = in + inlen - (inlen % sizeof (uint64_t)); + const int left = inlen & 7; + b = ((uint64_t) inlen) << 56; + v3 ^= k1; + v2 ^= k0; + v1 ^= k1; + v0 ^= k0; + +#ifdef CICN_SIPHASH_128 + v1 ^= 0xee; +#endif /* CICN_SIPHASH_128 */ + + for (; in != end; in += 8) + { + m = U8TO64_LE (in); + v3 ^= m; + + SIPTRACE; + for (i = 0; i < cROUNDS; ++i) + SIPROUND; + + v0 ^= m; + } + + switch (left) + { + case 7: + b |= ((uint64_t) in[6]) << 48; + case 6: + b |= ((uint64_t) in[5]) << 40; + case 5: + b |= ((uint64_t) in[4]) << 32; + case 4: + b |= ((uint64_t) in[3]) << 24; + case 3: + b |= ((uint64_t) in[2]) << 16; + case 2: + b |= ((uint64_t) in[1]) << 8; + case 1: + b |= ((uint64_t) in[0]); + break; + case 0: + break; + } + + v3 ^= b; + + SIPTRACE; + for (i = 0; i < cROUNDS; ++i) + SIPROUND; + + v0 ^= b; + +#ifndef CICN_SIPHASH_128 + v2 ^= 0xff; +#else + v2 ^= 0xee; +#endif /* CICN_SIPHASH_128 */ + + SIPTRACE; + for (i = 0; i < dROUNDS; ++i) + SIPROUND; + + return (v0 ^ v1 ^ v2 ^ v3); + +/* U64TO8_LE(out, b); TODO -- ref version mails back result and returns zero */ + +#ifdef CICN_SIPHASH_128 + v1 ^= 0xdd; + + SIPTRACE; + for (i = 0; i < dROUNDS; ++i) + SIPROUND; + + b = v0 ^ v1 ^ v2 ^ v3; + U64TO8_LE (out + 8, b); +#endif /* CICN_SIPHASH_128 */ + +/* return 0; TODO -- ref version mails back result and returns zero... */ +} + +/* + * Running state of hash, for taking advantage of incremental hashing + */ +typedef struct cicn_siphash_hi_s +{ + uint64_t sip_v_whole[4]; +} cicn_siphash_hi_t; + +/* + * cicn_siphash DOCUMENTATION (algorithm details) + * + * Sources: + * - Analysis: http://eprint.iacr.org/2012/351.pdf + * - Code: https://github.com/floodyberry/siphash + * + * siphash has an initialization phase, a compression phase, and a + * finalization phase. + * - The running state of siphash is stored in a "vector": 32 bytes, + * managed as a 4 element array of uint64_t. + * - The initialization phase initializes the vector ("V") for the + * hash calculation, based on the key and some constants + * - The compression phase processes the string to be hashed, + * processing an 8 byte (64 bit) block per iteration. Each + * interation includes + * - Convert the 8 bytes into a 64-bit number (using a little-endian + * conversion) + * - XOR the new 8 bytes into V[3] + * - Perform multiple (2) "rounds" of compression on V, using the logic + * in SipRound + * - XOR the new 8 bytes into V[0] + * - The last block is special. It is created as if extra bytes were + * available off the end of the string. The last block includes + * - leftover bytes at the tail of the string (e.g. 3 leftover bytes if + * the string were 11 bytes long) + * - nulls to fill out the tail of the string to 7 bytes (e.g. 4 nulls + * if the string were 11 bytes long) + * - The number of actual leftover bytes in the 8th byte (e.g. 3, + * if the string were 11 bytes long). + * - For another example, if the string were 8 bytes long, the last + * (2nd) block would be all null. + * - The finalization phase: + * - XOR 0xff info V[2] + * - Perform multiple (4) rounds of compression on V, using the + * logic in SipRound (i.e. compression and finalization use the same + * core compression logic) + * - XOR the 4 elements of V together to produce the 8 byte (64 bit) + * hash result. + */ + +const unsigned char cicn_siphash_seed[16] = { + 0x12, 0x34, 0x56, 0x78, 0x98, 0x76, 0x54, 0x32, + 0x12, 0x34, 0x56, 0x78, 0x98, 0x76, 0x54, 0x32, +}; + +/* + * Copy one siphash vector to another, e.g. to as part of saving a + * hash's intermediate result for later re-use. + * When processing a CICN name, calculating the siphashes of + * each component prefix plus the siphash of the whole name, this + * is used to keep track of partial results rather than doing + * each siphash from scratch (restarting at the beginning of the whole name). + * (See summary at "cicn_siphash DOCUMENTATION".) + * Returns: + * No return value + * Vout: + * Output vector, target of copy + * Vin: + * Input vector, source of copy + */ +#define cicn_siphash_vec_copy(Vout, Vin) do { \ + Vout[0] = Vin[0]; Vout[1] = Vin[1]; Vout[2] = Vin[2]; Vout[3] = Vin[3];\ + } while(0); + +static inline void +cicn_siphash_hi_initialize (cicn_siphash_hi_t * arg, + const unsigned char *seed) +{ + const unsigned char *key = seed; + uint64_t *V = arg->sip_v_whole; + uint64_t K[2]; + + K[0] = U8TO64_LE (&key[0]); + K[1] = U8TO64_LE (&key[8]); + + /* "somepseu""dorandom""lygenera""tedbytes" */ + V[0] = K[0] ^ 0x736f6d6570736575ull; + V[1] = K[1] ^ 0x646f72616e646f6dull; +#ifdef CICN_SIPHASH_128 + V[1] ^= 0xee; +#endif /* CICN_SIPHASH_128 */ + V[2] = K[0] ^ 0x6c7967656e657261ull; + V[3] = K[1] ^ 0x7465646279746573ull; +} + +/* + * The core logic of one round of siphash compression/finalization + * (See summary at "cicn_siphash DOCUMENTATION".) + * V: + * Vector holding the current state of the hash, to be put through + * (the core logic of) one round of compression/finalization. + */ +#define ROTL64(x,b) ROTL(x,b) +#define cicn_siphash_Round(V) { \ + V[0] += V[1]; V[2] += V[3]; \ + V[1] = ROTL64(V[1],13); V[3] = ROTL64(V[3],16); \ + V[1] ^= V[0]; V[3] ^= V[2]; \ + V[0] = ROTL64(V[0],32); \ + V[2] += V[1]; V[0] += V[3]; \ + V[1] = ROTL64(V[1],17); V[3] = ROTL64(V[3],21); \ + V[1] ^= V[2]; V[3] ^= V[0]; \ + V[2] = ROTL64(V[2],32); } + +/* + * The full logic of one round of siphash compression (not finalization) + * (See summary at "cicn_siphash DOCUMENTATION".) + */ +static inline void +cicn_siphash_compress (uint64_t V[4], uint64_t block_le_val) +{ + V[3] ^= block_le_val; + cicn_siphash_Round (V); + cicn_siphash_Round (V); + V[0] ^= block_le_val; +} + +/* + * At the end of a prefix/name/bytestring to be siphashed, 0-7 bytes will + * be left that do not make up a full 8-byte block. This routine + * convolves those 0-7 bytes with 1 byte derived from prefix overall length + * (not the count of trailing bytes) to get a last 64-bit quantity to be + * used in siphash finalization. + * + * @param[in] base is the base of the entire bytestring + * @param[in] len is the length of the entire bytestring + * @param[in] pblk_offset is the byte offset of the partial block (last + * 0-7 bytes) + * + * This routine, similar to the original code downloaded to siphash.c, + * is careful to not read any bytes past the end of the block + * (at the cost of doing multiple 1-byte reads rather than a single + * 8-byte read and mask). + * (See summary at "cicn_siphash DOCUMENTATION".) + */ +static inline uint64_t +cicn_siphash_partial_blk_val (const unsigned char *base, int len, + int pblk_offset) +{ + uint64_t pblk_val_64_LE; + int partial_bytes = (len & 0x7); + + pblk_val_64_LE = (uint64_t) (len & 0xff) << 56; + switch (partial_bytes) + { + case 7: + pblk_val_64_LE |= (uint64_t) base[pblk_offset + 6] << 48; + case 6: + pblk_val_64_LE |= (uint64_t) base[pblk_offset + 5] << 40; + case 5: + pblk_val_64_LE |= (uint64_t) base[pblk_offset + 4] << 32; + case 4: + pblk_val_64_LE |= (uint64_t) base[pblk_offset + 3] << 24; + case 3: + pblk_val_64_LE |= (uint64_t) base[pblk_offset + 2] << 16; + case 2: + pblk_val_64_LE |= (uint64_t) base[pblk_offset + 1] << 8; + case 1: + pblk_val_64_LE |= (uint64_t) base[pblk_offset + 0]; + case 0: + default:; + } + return (pblk_val_64_LE); +} + +/* + * The logic for convolving the final/partial 8-byte/64-bit block into + * the running 32-byte vector, which is then xor'd ito the 64-bit hash value. + * (See summary at "cicn_siphash DOCUMENTATION".) + */ +static inline uint64_t +cicn_siphash_finalize (uint64_t V[4]) +{ + uint64_t hash; + +#ifndef CICN_SIPHASH_128 + V[2] ^= 0xff; +#else + V[2] ^= 0xee; +#endif /* CICN_SIPHASH_128 */ + + cicn_siphash_Round (V); + cicn_siphash_Round (V); + cicn_siphash_Round (V); + cicn_siphash_Round (V); + hash = V[0] ^ V[1] ^ V[2] ^ V[3]; + return (hash); + +#ifdef CICN_SIPHASH_128 + V[1] ^= 0xdd; + + cicn_hfn_sip_Round (V); + cicn_hfn_sip_Round (V); + cicn_hfn_sip_Round (V); + cicn_hfn_sip_Round (V); + + hash = V[0] ^ V[1] ^ V[2] ^ V[3]; + U64TO8_LE (out + 8, hash); +#endif /* CICN_SIPHASH_128 */ +} + +/* + * Calculate/return 64-bit siphash of bytestring (name prefix) beginning at + * nrec_val with length pfx_len, for which intermediate siphash + * information through crec_offset is already stored in V_running. + * (In other words, this optimized siphash calculation need only + * convolve the last pfx_len-crec_offset bytes of + * prefix into the calculation.) + * + * As an important side effect, V_running is updated with siphash + * information through the final full 8-byte block in the prefix, for + * use in calculating the siphash of the following prefix. + * + * (See summary at "cicn_siphash DOCUMENTATION".) + */ +static inline uint64_t +cicn_siphash_hi_calculate (cicn_siphash_hi_t * arg, + const unsigned char *nrec_val, int pfx_len, + int crec_offset) +{ + uint64_t *V_running = arg->sip_v_whole; + + uint64_t hash; + size_t cur_crec_base_blk, next_crec_base_blk, blk; + uint64_t V_finalize[4]; + + //printf("cur_crec_base_blk: %d ", cur_crec_base_blk); + + /* blks (8 bytes) are byte offsets: they count 0,8,16... not 0,1,2... */ + cur_crec_base_blk = (crec_offset & ~7); + next_crec_base_blk = (pfx_len & ~7); + for (blk = cur_crec_base_blk; blk < next_crec_base_blk; blk += 8) + { + cicn_siphash_compress (V_running, U8TO64_LE (&nrec_val[blk])); + } + + /* copy V to v to finalize hash calculation for this prefix */ + cicn_siphash_vec_copy (V_finalize, V_running); + + cicn_siphash_compress (V_finalize, + cicn_siphash_partial_blk_val (nrec_val, pfx_len, + blk)); + hash = cicn_siphash_finalize (V_finalize); + + return (hash); +} + +#endif /* _CICN_SIPHASH_H_ */ |