chiark - git - mdw - mLib/blob - hash/t/hash-test.c

   1 /* -*-c-*-
   2  *
   3  * Test driver for universal hashing
   4  *
   5  * (c) 2009 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of the mLib utilities library.
  11  *
  12  * mLib is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * mLib is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with mLib; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include "tvec.h"
  31 #include "tvec-bench.h"
  32 #include "tvec-types.h"
  33
  34 #include "crc32.h"
  35 #include "siphash.h"
  36 #include "unihash.h"
  37
  38 /*----- Register allocation -----------------------------------------------*/
  39
  40 enum {
  41   RH, NROUT,
  42   RK = NROUT, RM, NREG
  43 };
  44
  45 /*----- Testing utilities -------------------------------------------------*/
  46
  47 struct step { size_t s; };
  48
  49 static void run_step(struct tvec_state *tv, tvec_testfn *fn, void *ctx)
  50 {
  51   static const size_t steps[] = { 1, 5, 6, 7, 8, 23 };
  52   struct step step;
  53   size_t i;
  54
  55   fn(tv->in, tv->out, 0);
  56   tvec_check(tv, "whole buffer");
  57
  58   for (i = 0; i < N(steps); i++) {
  59     step.s = steps[i];
  60     fn(tv->in, tv->out, &step);
  61     tvec_check(tv, "step = %lu", (unsigned long)steps[i]);
  62   }
  63 }
  64
  65 static const struct tvec_env step_testenv = { 0, 0, 0, 0, run_step, 0, 0 };
  66
  67 static void before_hash(struct tvec_state *tv, void *ctx)
  68   { tvec_allocbuffer(&tv->in[RM].v); }
  69
  70 /*----- CRC32 -------------------------------------------------------------*/
  71
  72 static const struct tvec_regdef bench_regs[] = {
  73   { "msz", &tvty_buffer, RM, TVRF_ID },
  74   TVEC_ENDREGS
  75 };
  76
  77 static const struct tvec_regdef crc32_regs[] = {
  78   { "m", &tvty_bytes, RM, 0 },
  79   { "h", &tvty_uint, RH, 0, { &tvrange_u32 } },
  80   TVEC_ENDREGS
  81 };
  82
  83 static void test_crc32(const struct tvec_reg *in, struct tvec_reg *out,
  84                        void *ctx)
  85 {
  86   const struct step *step = ctx;
  87   const unsigned char *p = in[RM].v.bytes.p; size_t sz = in[RM].v.bytes.sz;
  88   uint32 h;
  89
  90   if (!step)
  91     out[RH].v.u = crc32(0, p, sz);
  92   else {
  93     for (h = 0; sz > step->s; p += step->s, sz -= step->s)
  94       h = crc32(h, p, step->s);
  95     out[RH].v.u = crc32(h, p, sz);
  96   }
  97 }
  98
  99 static const struct tvec_test crc32_test =
 100   { "crc32", crc32_regs, &step_testenv, test_crc32 };
 101
 102 static void bench_crc32(const struct tvec_reg *in, struct tvec_reg *out,
 103                         void *ctx)
 104   { crc32(0, in[RM].v.bytes.p, in[RM].v.bytes.sz); }
 105
 106 static const struct tvec_env crc32_benchenv =
 107   { 0, 0, 0, before_hash };
 108 static const struct tvec_benchenv crc32_bench =
 109   { TVEC_BENCHINIT, 1, -1, RM, &crc32_benchenv };
 110 static const struct tvec_test crc32_benchtest =
 111   { "crc32-bench", bench_regs, &crc32_bench._env, bench_crc32 };
 112
 113 /*----- SipHash -----------------------------------------------------------*/
 114
 115 static const struct tvec_urange
 116   siphash_keyrange = { SIPHASH_KEYSZ, SIPHASH_KEYSZ },
 117   siphash_hashrange = { 8, 8 };
 118
 119 static const struct tvec_regdef siphash_regs[] = {
 120   { "k", &tvty_bytes, RK, 0, { &siphash_keyrange } },
 121   { "m", &tvty_bytes, RM, 0 },
 122   { "h", &tvty_bytes, RH, 0, { &siphash_hashrange } },
 123   TVEC_ENDREGS
 124 };
 125
 126 #define TEST_SIPHASH(nr0, nr1)                                          \
 127                                                                         \
 128   static void test_siphash##nr0##nr1(const struct tvec_reg *in,         \
 129                                      struct tvec_reg *out,              \
 130                                      void *ctx)                         \
 131   {                                                                     \
 132     const struct step *step = ctx;                                      \
 133     const unsigned char *p = in[RM].v.bytes.p;                          \
 134     size_t sz = in[RM].v.bytes.sz;                                      \
 135     struct siphash_key k;                                               \
 136     struct siphash##nr0##nr1 s;                                         \
 137     kludge64 h;                                                         \
 138                                                                         \
 139     siphash_setkey(&k, in[RK].v.bytes.p);                               \
 140     if (!step)                                                          \
 141       h = siphash##nr0##nr1(&k, p, sz);                                 \
 142     else {                                                              \
 143       siphash##nr0##nr1##_init(&s, &k);                                 \
 144       for (; sz > step->s; p += step->s, sz -= step->s)                 \
 145         siphash##nr0##nr1##_hash(&s, p, step->s);                       \
 146       siphash##nr0##nr1##_hash(&s, p, sz);                              \
 147       h = siphash##nr0##nr1##_done(&s);                                 \
 148     }                                                                   \
 149     tvec_allocbytes(&out[RH].v, 8); STORE64_L_(out[RH].v.bytes.p, h);   \
 150   }                                                                     \
 151                                                                         \
 152   static const struct tvec_test siphash##nr0##nr1##_test =              \
 153     { "siphash" #nr0 #nr1, siphash_regs,                                \
 154       &step_testenv, test_siphash##nr0##nr1 };
 155
 156 SIPHASH_VARIANTS(TEST_SIPHASH)
 157
 158 #define SIPHASH_TEST(nr0, nr1) &siphash##nr0##nr1##_test,
 159
 160 static void setup_siphash(struct tvec_state *tv,
 161                           const struct tvec_env *env, void *pctx, void *ctx)
 162 {
 163   struct siphash_key *k = ctx;
 164   ASSIGN64(k->k0, 0); ASSIGN64(k->k1, 0);
 165 }
 166
 167 static const struct tvec_env siphash_benchenv =
 168   { sizeof(struct siphash_key), setup_siphash, 0, before_hash };
 169 static const struct tvec_benchenv siphash_bench =
 170   { TVEC_BENCHINIT, 1, -1, RM, &siphash_benchenv };
 171
 172 #define BENCH_SIPHASH(nr0, nr1)                                         \
 173                                                                         \
 174   static void bench_siphash##nr0##nr1(const struct tvec_reg *in,        \
 175                                       struct tvec_reg *out,             \
 176                                       void *ctx)                        \
 177   { siphash##nr0##nr1(ctx, in[RM].v.bytes.p, in[RM].v.bytes.sz); }      \
 178                                                                         \
 179   static const struct tvec_test siphash##nr0##nr1##_benchtest =         \
 180     { "siphash" #nr0 #nr1 "-bench", bench_regs,                         \
 181       &siphash_bench._env, bench_siphash##nr0##nr1 };
 182
 183 SIPHASH_VARIANTS(BENCH_SIPHASH)
 184
 185 #define SIPHASH_BENCH(nr0, nr1) &siphash##nr0##nr1##_benchtest,
 186
 187 /*----- Unihash -----------------------------------------------------------*/
 188
 189 static const struct tvec_regdef unihash_regs[] = {
 190   { "k", &tvty_uint, RK, 0, { &tvrange_u32 } },
 191   { "m", &tvty_bytes, RM, 0 },
 192   { "h", &tvty_uint, RH, 0, { &tvrange_u32 } },
 193   TVEC_ENDREGS
 194 };
 195
 196 static void test_unihash(const struct tvec_reg *in, struct tvec_reg *out,
 197                          void *ctx)
 198 {
 199   const struct step *step = ctx;
 200   unihash_info ui;
 201   const unsigned char *p = in[RM].v.bytes.p; size_t sz = in[RM].v.bytes.sz;
 202   uint32 h;
 203
 204   unihash_setkey(&ui, in[RK].v.u);
 205   if (!step)
 206     out[RH].v.u = unihash(&ui, p, sz);
 207   else {
 208     for (h = UNIHASH_INIT(&ui); sz > step->s; p += step->s, sz -= step->s)
 209       h = unihash_hash(&ui, h, p, step->s);
 210     out[RH].v.u = unihash_hash(&ui, h, p, sz);
 211   }
 212 }
 213
 214 static const struct tvec_test unihash_test =
 215   { "unihash", unihash_regs, &step_testenv, test_unihash };
 216
 217 static void setup_unihash(struct tvec_state *tv,
 218                           const struct tvec_env *env, void *pctx, void *ctx)
 219   { unihash_setkey(ctx, 0); }
 220
 221 static void bench_unihash(const struct tvec_reg *in, struct tvec_reg *out,
 222                           void *ctx)
 223   { unihash_hash(ctx, 0, in[RM].v.bytes.p, in[RM].v.bytes.sz); }
 224
 225 static const struct tvec_env unihash_benchenv =
 226   { sizeof(unihash_info), setup_unihash, 0, before_hash };
 227 static const struct tvec_benchenv unihash_bench =
 228   { TVEC_BENCHINIT, 1, -1, RM, &unihash_benchenv };
 229 static const struct tvec_test unihash_benchtest =
 230   { "unihash-bench", bench_regs, &unihash_bench._env, bench_unihash };
 231
 232 /*----- Main program ------------------------------------------------------*/
 233
 234 static const struct tvec_test *const tests[] = {
 235   &crc32_test, &crc32_benchtest,
 236   SIPHASH_VARIANTS(SIPHASH_TEST) SIPHASH_VARIANTS(SIPHASH_BENCH)
 237   &unihash_test, &unihash_benchtest,
 238   0
 239 };
 240
 241 static const struct tvec_config testconfig =
 242   { tests, NROUT, NREG, sizeof(struct tvec_reg) };
 243
 244 int main(int argc, char *argv[])
 245   { return (tvec_main(argc, argv, &testconfig, 0)); }
 246
 247 /*----- That's all, folks -------------------------------------------------*/