1 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */ 2 /* util/support/t_hash.c - tests for hash table code */ 3 /* 4 * Copyright (C) 2018 by the Massachusetts Institute of Technology. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 14 * * Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in 16 * the documentation and/or other materials provided with the 17 * distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 22 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 23 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 24 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 25 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 26 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 28 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 30 * OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 /* hash.c has no linker dependencies, so we can simply include its source code 34 * to test its static functions and look inside its structures. */ 35 #include "hashtab.c" 36 37 /* These match the sip64 test vectors in the reference C implementation of 38 * siphash at https://github.com/veorq/SipHash */ 39 const uint64_t vectors[64] = { 40 0x726FDB47DD0E0E31, 41 0x74F839C593DC67FD, 42 0x0D6C8009D9A94F5A, 43 0x85676696D7FB7E2D, 44 0xCF2794E0277187B7, 45 0x18765564CD99A68D, 46 0xCBC9466E58FEE3CE, 47 0xAB0200F58B01D137, 48 0x93F5F5799A932462, 49 0x9E0082DF0BA9E4B0, 50 0x7A5DBBC594DDB9F3, 51 0xF4B32F46226BADA7, 52 0x751E8FBC860EE5FB, 53 0x14EA5627C0843D90, 54 0xF723CA908E7AF2EE, 55 0xA129CA6149BE45E5, 56 0x3F2ACC7F57C29BDB, 57 0x699AE9F52CBE4794, 58 0x4BC1B3F0968DD39C, 59 0xBB6DC91DA77961BD, 60 0xBED65CF21AA2EE98, 61 0xD0F2CBB02E3B67C7, 62 0x93536795E3A33E88, 63 0xA80C038CCD5CCEC8, 64 0xB8AD50C6F649AF94, 65 0xBCE192DE8A85B8EA, 66 0x17D835B85BBB15F3, 67 0x2F2E6163076BCFAD, 68 0xDE4DAAACA71DC9A5, 69 0xA6A2506687956571, 70 0xAD87A3535C49EF28, 71 0x32D892FAD841C342, 72 0x7127512F72F27CCE, 73 0xA7F32346F95978E3, 74 0x12E0B01ABB051238, 75 0x15E034D40FA197AE, 76 0x314DFFBE0815A3B4, 77 0x027990F029623981, 78 0xCADCD4E59EF40C4D, 79 0x9ABFD8766A33735C, 80 0x0E3EA96B5304A7D0, 81 0xAD0C42D6FC585992, 82 0x187306C89BC215A9, 83 0xD4A60ABCF3792B95, 84 0xF935451DE4F21DF2, 85 0xA9538F0419755787, 86 0xDB9ACDDFF56CA510, 87 0xD06C98CD5C0975EB, 88 0xE612A3CB9ECBA951, 89 0xC766E62CFCADAF96, 90 0xEE64435A9752FE72, 91 0xA192D576B245165A, 92 0x0A8787BF8ECB74B2, 93 0x81B3E73D20B49B6F, 94 0x7FA8220BA3B2ECEA, 95 0x245731C13CA42499, 96 0xB78DBFAF3A8D83BD, 97 0xEA1AD565322A1A0B, 98 0x60E61C23A3795013, 99 0x6606D7E446282B93, 100 0x6CA4ECB15C5F91E1, 101 0x9F626DA15C9625F3, 102 0xE51B38608EF25F57, 103 0x958A324CEB064572 104 }; 105 106 static void 107 test_siphash() 108 { 109 uint8_t seq[64]; 110 uint64_t k0, k1, hval; 111 size_t i; 112 113 for (i = 0; i < sizeof(seq); i++) 114 seq[i] = i; 115 k0 = load_64_le(seq); 116 k1 = load_64_le(seq + 8); 117 118 for (i = 0; i < sizeof(seq); i++) { 119 hval = siphash24(seq, i, k0, k1); 120 assert(hval == vectors[i]); 121 } 122 } 123 124 static void 125 test_hashtab() 126 { 127 int st; 128 struct k5_hashtab *ht; 129 size_t i; 130 char zeros[100] = { 0 }; 131 132 st = k5_hashtab_create(NULL, 4, &ht); 133 assert(st == 0 && ht != NULL && ht->nentries == 0); 134 135 st = k5_hashtab_add(ht, "abc", 3, &st); 136 assert(st == 0 && ht->nentries == 1); 137 assert(k5_hashtab_get(ht, "abc", 3) == &st); 138 assert(k5_hashtab_get(ht, "bcde", 4) == NULL); 139 140 st = k5_hashtab_add(ht, "bcde", 4, &ht); 141 assert(st == 0 && ht->nentries == 2); 142 assert(k5_hashtab_get(ht, "abc", 3) == &st); 143 assert(k5_hashtab_get(ht, "bcde", 4) == &ht); 144 145 k5_hashtab_remove(ht, "abc", 3); 146 assert(ht->nentries == 1); 147 assert(k5_hashtab_get(ht, "abc", 3) == NULL); 148 assert(k5_hashtab_get(ht, "bcde", 4) == &ht); 149 150 k5_hashtab_remove(ht, "bcde", 4); 151 assert(ht->nentries == 0); 152 assert(k5_hashtab_get(ht, "abc", 3) == NULL); 153 assert(k5_hashtab_get(ht, "bcde", 4) == NULL); 154 155 for (i = 0; i < sizeof(zeros); i++) { 156 st = k5_hashtab_add(ht, zeros, i, zeros + i); 157 assert(st == 0 && ht->nentries == i + 1 && ht->nbuckets >= i + 1); 158 } 159 for (i = 0; i < sizeof(zeros); i++) { 160 assert(k5_hashtab_get(ht, zeros, i) == zeros + i); 161 k5_hashtab_remove(ht, zeros, i); 162 assert(ht->nentries == sizeof(zeros) - i - 1); 163 if (i > 0) 164 assert(k5_hashtab_get(ht, zeros, i - 1) == NULL); 165 } 166 167 k5_hashtab_free(ht); 168 } 169 170 int 171 main() 172 { 173 test_siphash(); 174 test_hashtab(); 175 return 0; 176 } 177