This file is indexed.

/usr/include/mozjs-24/mozilla/HashFunctions.h is in libmozjs-24-dev 24.2.0-3ubuntu2.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
 * You can obtain one at http://mozilla.org/MPL/2.0/. */

/* Utilities for hashing. */

/*
 * This file exports functions for hashing data down to a 32-bit value,
 * including:
 *
 *  - HashString    Hash a char* or uint16_t/wchar_t* of known or unknown
 *                  length.
 *
 *  - HashBytes     Hash a byte array of known length.
 *
 *  - HashGeneric   Hash one or more values.  Currently, we support uint32_t,
 *                  types which can be implicitly cast to uint32_t, data
 *                  pointers, and function pointers.
 *
 *  - AddToHash     Add one or more values to the given hash.  This supports the
 *                  same list of types as HashGeneric.
 *
 *
 * You can chain these functions together to hash complex objects.  For example:
 *
 *  class ComplexObject
 *  {
 *      char* str;
 *      uint32_t uint1, uint2;
 *      void (*callbackFn)();
 *
 *    public:
 *      uint32_t hash() {
 *        uint32_t hash = HashString(str);
 *        hash = AddToHash(hash, uint1, uint2);
 *        return AddToHash(hash, callbackFn);
 *      }
 *  };
 *
 * If you want to hash an nsAString or nsACString, use the HashString functions
 * in nsHashKeys.h.
 */

#ifndef mozilla_HashFunctions_h_
#define mozilla_HashFunctions_h_

#include "mozilla/Assertions.h"
#include "mozilla/Attributes.h"
#include "mozilla/StandardInteger.h"
#include "mozilla/Types.h"

#ifdef __cplusplus
namespace mozilla {

/**
 * The golden ratio as a 32-bit fixed-point value.
 */
static const uint32_t GoldenRatioU32 = 0x9E3779B9U;

inline uint32_t
RotateBitsLeft32(uint32_t value, uint8_t bits)
{
  MOZ_ASSERT(bits < 32);
  return (value << bits) | (value >> (32 - bits));
}

namespace detail {

inline uint32_t
AddU32ToHash(uint32_t hash, uint32_t value)
{
  /*
   * This is the meat of all our hash routines.  This hash function is not
   * particularly sophisticated, but it seems to work well for our mostly
   * plain-text inputs.  Implementation notes follow.
   *
   * Our use of the golden ratio here is arbitrary; we could pick almost any
   * number which:
   *
   *  * is odd (because otherwise, all our hash values will be even)
   *
   *  * has a reasonably-even mix of 1's and 0's (consider the extreme case
   *    where we multiply by 0x3 or 0xeffffff -- this will not produce good
   *    mixing across all bits of the hash).
   *
   * The rotation length of 5 is also arbitrary, although an odd number is again
   * preferable so our hash explores the whole universe of possible rotations.
   *
   * Finally, we multiply by the golden ratio *after* xor'ing, not before.
   * Otherwise, if |hash| is 0 (as it often is for the beginning of a message),
   * the expression
   *
   *   (GoldenRatioU32 * RotateBitsLeft(hash, 5)) |xor| value
   *
   * evaluates to |value|.
   *
   * (Number-theoretic aside: Because any odd number |m| is relatively prime to
   * our modulus (2^32), the list
   *
   *    [x * m (mod 2^32) for 0 <= x < 2^32]
   *
   * has no duplicate elements.  This means that multiplying by |m| does not
   * cause us to skip any possible hash values.
   *
   * It's also nice if |m| has large-ish order mod 2^32 -- that is, if the
   * smallest k such that m^k == 1 (mod 2^32) is large -- so we can safely
   * multiply our hash value by |m| a few times without negating the
   * multiplicative effect.  Our golden ratio constant has order 2^29, which is
   * more than enough for our purposes.)
   */
  return GoldenRatioU32 * (RotateBitsLeft32(hash, 5) ^ value);
}

/**
 * AddUintptrToHash takes sizeof(uintptr_t) as a template parameter.
 */
template<size_t PtrSize>
inline uint32_t
AddUintptrToHash(uint32_t hash, uintptr_t value);

template<>
inline uint32_t
AddUintptrToHash<4>(uint32_t hash, uintptr_t value)
{
  return AddU32ToHash(hash, static_cast<uint32_t>(value));
}

template<>
inline uint32_t
AddUintptrToHash<8>(uint32_t hash, uintptr_t value)
{
  /*
   * The static cast to uint64_t below is necessary because this function
   * sometimes gets compiled on 32-bit platforms (yes, even though it's a
   * template and we never call this particular override in a 32-bit build).  If
   * we do value >> 32 on a 32-bit machine, we're shifting a 32-bit uintptr_t
   * right 32 bits, and the compiler throws an error.
   */
  uint32_t v1 = static_cast<uint32_t>(value);
  uint32_t v2 = static_cast<uint32_t>(static_cast<uint64_t>(value) >> 32);
  return AddU32ToHash(AddU32ToHash(hash, v1), v2);
}

} /* namespace detail */

/**
 * AddToHash takes a hash and some values and returns a new hash based on the
 * inputs.
 *
 * Currently, we support hashing uint32_t's, values which we can implicitly
 * convert to uint32_t, data pointers, and function pointers.
 */
template<typename A>
MOZ_WARN_UNUSED_RESULT
inline uint32_t
AddToHash(uint32_t hash, A a)
{
  /*
   * Try to convert |A| to uint32_t implicitly.  If this works, great.  If not,
   * we'll error out.
   */
  return detail::AddU32ToHash(hash, a);
}

template<typename A>
MOZ_WARN_UNUSED_RESULT
inline uint32_t
AddToHash(uint32_t hash, A* a)
{
  /*
   * You might think this function should just take a void*.  But then we'd only
   * catch data pointers and couldn't handle function pointers.
   */

  MOZ_STATIC_ASSERT(sizeof(a) == sizeof(uintptr_t),
                    "Strange pointer!");

  return detail::AddUintptrToHash<sizeof(uintptr_t)>(hash, uintptr_t(a));
}

template<>
MOZ_WARN_UNUSED_RESULT
inline uint32_t
AddToHash(uint32_t hash, uintptr_t a)
{
  return detail::AddUintptrToHash<sizeof(uintptr_t)>(hash, a);
}

template<typename A, typename B>
MOZ_WARN_UNUSED_RESULT
uint32_t
AddToHash(uint32_t hash, A a, B b)
{
  return AddToHash(AddToHash(hash, a), b);
}

template<typename A, typename B, typename C>
MOZ_WARN_UNUSED_RESULT
uint32_t
AddToHash(uint32_t hash, A a, B b, C c)
{
  return AddToHash(AddToHash(hash, a, b), c);
}

template<typename A, typename B, typename C, typename D>
MOZ_WARN_UNUSED_RESULT
uint32_t
AddToHash(uint32_t hash, A a, B b, C c, D d)
{
  return AddToHash(AddToHash(hash, a, b, c), d);
}

template<typename A, typename B, typename C, typename D, typename E>
MOZ_WARN_UNUSED_RESULT
uint32_t
AddToHash(uint32_t hash, A a, B b, C c, D d, E e)
{
  return AddToHash(AddToHash(hash, a, b, c, d), e);
}

/**
 * The HashGeneric class of functions let you hash one or more values.
 *
 * If you want to hash together two values x and y, calling HashGeneric(x, y) is
 * much better than calling AddToHash(x, y), because AddToHash(x, y) assumes
 * that x has already been hashed.
 */
template<typename A>
MOZ_WARN_UNUSED_RESULT
inline uint32_t
HashGeneric(A a)
{
  return AddToHash(0, a);
}

template<typename A, typename B>
MOZ_WARN_UNUSED_RESULT
inline uint32_t
HashGeneric(A a, B b)
{
  return AddToHash(0, a, b);
}

template<typename A, typename B, typename C>
MOZ_WARN_UNUSED_RESULT
inline uint32_t
HashGeneric(A a, B b, C c)
{
  return AddToHash(0, a, b, c);
}

template<typename A, typename B, typename C, typename D>
MOZ_WARN_UNUSED_RESULT
inline uint32_t
HashGeneric(A a, B b, C c, D d)
{
  return AddToHash(0, a, b, c, d);
}

template<typename A, typename B, typename C, typename D, typename E>
MOZ_WARN_UNUSED_RESULT
inline uint32_t
HashGeneric(A a, B b, C c, D d, E e)
{
  return AddToHash(0, a, b, c, d, e);
}

namespace detail {

template<typename T>
uint32_t
HashUntilZero(const T* str)
{
  uint32_t hash = 0;
  for (T c; (c = *str); str++)
    hash = AddToHash(hash, c);
  return hash;
}

template<typename T>
uint32_t
HashKnownLength(const T* str, size_t length)
{
  uint32_t hash = 0;
  for (size_t i = 0; i < length; i++)
    hash = AddToHash(hash, str[i]);
  return hash;
}

} /* namespace detail */

/**
 * The HashString overloads below do just what you'd expect.
 *
 * If you have the string's length, you might as well call the overload which
 * includes the length.  It may be marginally faster.
 */
MOZ_WARN_UNUSED_RESULT
inline uint32_t
HashString(const char* str)
{
  return detail::HashUntilZero(str);
}

MOZ_WARN_UNUSED_RESULT
inline uint32_t
HashString(const char* str, size_t length)
{
  return detail::HashKnownLength(str, length);
}

MOZ_WARN_UNUSED_RESULT
inline uint32_t
HashString(const uint16_t* str)
{
  return detail::HashUntilZero(str);
}

MOZ_WARN_UNUSED_RESULT
inline uint32_t
HashString(const uint16_t* str, size_t length)
{
  return detail::HashKnownLength(str, length);
}

/*
 * On Windows, wchar_t (PRUnichar) is not the same as uint16_t, even though it's
 * the same width!
 */
#ifdef WIN32
MOZ_WARN_UNUSED_RESULT
inline uint32_t
HashString(const wchar_t* str)
{
  return detail::HashUntilZero(str);
}

MOZ_WARN_UNUSED_RESULT
inline uint32_t
HashString(const wchar_t* str, size_t length)
{
  return detail::HashKnownLength(str, length);
}
#endif

/**
 * Hash some number of bytes.
 *
 * This hash walks word-by-word, rather than byte-by-byte, so you won't get the
 * same result out of HashBytes as you would out of HashString.
 */
MOZ_WARN_UNUSED_RESULT
extern MFBT_API uint32_t
HashBytes(const void* bytes, size_t length);

} /* namespace mozilla */
#endif /* __cplusplus */
#endif /* mozilla_HashFunctions_h_ */