• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1'use strict';
2function run_repeated(n, fn) {
3  const res = [];
4  for (let i = 0; i < n; i++) res.push(fn());
5  return res;
6}
7
8const INT_MAX = 0x7fffffff;
9
10// from src/js/collection.js
11// key must be a signed 32-bit number!
12function ComputeIntegerHash(key/*, seed*/) {
13  let hash = key;
14  hash = hash ^ 0/*seed*/;
15  hash = ~hash + (hash << 15);  // hash = (hash << 15) - hash - 1;
16  hash = hash ^ (hash >>> 12);
17  hash = hash + (hash << 2);
18  hash = hash ^ (hash >>> 4);
19  hash = (hash * 2057) | 0;  // hash = (hash + (hash << 3)) + (hash << 11);
20  hash = hash ^ (hash >>> 16);
21  return hash & 0x3fffffff;
22}
23
24const kNofHashBitFields = 2;
25const kHashShift = kNofHashBitFields;
26const kHashBitMask = 0xffffffff >>> kHashShift;
27const kZeroHash = 27;
28
29function string_to_array(str) {
30  const res = new Array(str.length);
31  for (let i = 0; i < str.length; i++) {
32    res[i] = str.charCodeAt(i);
33  }
34  return res;
35}
36
37function gen_specialized_hasher(str) {
38  const str_arr = string_to_array(str);
39  return Function('seed', `
40    var running_hash = seed;
41    ${str_arr.map((c) => `
42      running_hash += ${c};
43      running_hash &= 0xffffffff;
44      running_hash += (running_hash << 10);
45      running_hash &= 0xffffffff;
46      running_hash ^= (running_hash >>> 6);
47      running_hash &= 0xffffffff;
48    `).join('')}
49    running_hash += (running_hash << 3);
50    running_hash &= 0xffffffff;
51    running_hash ^= (running_hash >>> 11);
52    running_hash &= 0xffffffff;
53    running_hash += (running_hash << 15);
54    running_hash &= 0xffffffff;
55    if ((running_hash & ${kHashBitMask}) == 0) {
56      return ${kZeroHash};
57    }
58    return running_hash;
59  `);
60}
61
62// adapted from HashToEntry
63function hash_to_bucket(hash, numBuckets) {
64  return (hash & ((numBuckets) - 1));
65}
66
67function time_set_lookup(set, value) {
68  const t1 = process.hrtime();
69  for (let i = 0; i < 100; i++) {
70    // annoyingly, SetHas() is JS code and therefore potentially optimizable.
71    // However, SetHas() looks up the table using native code, and it seems like
72    // that's sufficient to prevent the optimizer from doing anything?
73    set.has(value);
74  }
75  const t = process.hrtime(t1);
76  const secs = t[0];
77  const nanos = t[1];
78  return secs * 1e9 + nanos;
79}
80
81// Set with 256 buckets; bucket 0 full, others empty
82const tester_set_buckets = 256;
83const tester_set = new Set();
84let tester_set_treshold;
85(function() {
86  // fill bucket 0 and find extra numbers mapping to bucket 0 and a different
87  // bucket `capacity == numBuckets * 2`
88  let needed = Math.floor(tester_set_buckets * 1.5) + 1;
89  let positive_test_value;
90  let negative_test_value;
91  for (let i = 0; true; i++) {
92    if (i > INT_MAX) throw new Error('i too high');
93    if (hash_to_bucket(ComputeIntegerHash(i), tester_set_buckets) !== 0) {
94      negative_test_value = i;
95      break;
96    }
97  }
98  for (let i = 0; needed > 0; i++) {
99    if (i > INT_MAX) throw new Error('i too high');
100    if (hash_to_bucket(ComputeIntegerHash(i), tester_set_buckets) === 0) {
101      needed--;
102      if (needed == 0) {
103        positive_test_value = i;
104      } else {
105        tester_set.add(i);
106      }
107    }
108  }
109
110  // calibrate Set access times for accessing the full bucket / an empty bucket
111  const pos_time =
112    Math.min(...run_repeated(10000, time_set_lookup.bind(null, tester_set,
113                                                         positive_test_value)));
114  const neg_time =
115    Math.min(...run_repeated(10000, time_set_lookup.bind(null, tester_set,
116                                                         negative_test_value)));
117  tester_set_treshold = (pos_time + neg_time) / 2;
118  // console.log(`pos_time: ${pos_time}, neg_time: ${neg_time},`,
119  //             `threshold: ${tester_set_treshold}`);
120})();
121
122// determine hash seed
123const slow_str_gen = (function*() {
124  let strgen_i = 0;
125  outer:
126  while (1) {
127    const str = `#${strgen_i++}`;
128    for (let i = 0; i < 1000; i++) {
129      if (time_set_lookup(tester_set, str) < tester_set_treshold)
130        continue outer;
131    }
132    yield str;
133  }
134})();
135
136const first_slow_str = slow_str_gen.next().value;
137// console.log('first slow string:', first_slow_str);
138const first_slow_str_special_hasher = gen_specialized_hasher(first_slow_str);
139let seed_candidates = [];
140//var t_before_first_seed_brute = performance.now();
141for (let seed_candidate = 0; seed_candidate < 0x100000000; seed_candidate++) {
142  if (hash_to_bucket(first_slow_str_special_hasher(seed_candidate),
143                     tester_set_buckets) == 0) {
144    seed_candidates.push(seed_candidate);
145  }
146}
147// console.log(`got ${seed_candidates.length} candidates`);
148//  after ${performance.now()-t_before_first_seed_brute}
149while (seed_candidates.length > 1) {
150  const slow_str = slow_str_gen.next().value;
151  const special_hasher = gen_specialized_hasher(slow_str);
152  const new_seed_candidates = [];
153  for (const seed_candidate of seed_candidates) {
154    if (hash_to_bucket(special_hasher(seed_candidate), tester_set_buckets) ==
155        0) {
156      new_seed_candidates.push(seed_candidate);
157    }
158  }
159  seed_candidates = new_seed_candidates;
160  // console.log(`reduced to ${seed_candidates.length} candidates`);
161}
162if (seed_candidates.length != 1)
163  throw new Error('no candidates remaining');
164const seed = seed_candidates[0];
165console.log(seed);
166