summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--std/hash/_fnv/fnv32.ts79
-rw-r--r--std/hash/_fnv/fnv64.ts89
-rw-r--r--std/hash/_fnv/util.ts52
-rw-r--r--std/hash/_fnv/util_test.ts71
-rw-r--r--std/hash/fnv.ts4
-rw-r--r--std/hash/fnv_test.ts113
6 files changed, 408 insertions, 0 deletions
diff --git a/std/hash/_fnv/fnv32.ts b/std/hash/_fnv/fnv32.ts
new file mode 100644
index 000000000..9547e1199
--- /dev/null
+++ b/std/hash/_fnv/fnv32.ts
@@ -0,0 +1,79 @@
+// Ported from Go:
+// https://github.com/golang/go/tree/go1.13.10/src/hash/fnv/fnv.go
+// Copyright 2011 The Go Authors. All rights reserved. BSD license.
+// https://github.com/golang/go/blob/master/LICENSE
+// Copyright 2018-2020 the Deno authors. All rights reserved. MIT license.
+
+import { mul32 } from "./util.ts";
+
+const offset32 = 2166136261;
+const prime32 = 16777619;
+
+abstract class Fnv32Base<T> {
+ #state: number;
+
+ constructor() {
+ this.#state = offset32;
+ }
+
+ protected _updateState(newState: number): void {
+ this.#state = newState;
+ }
+
+ reset(): void {
+ this.#state = offset32;
+ }
+
+ abstract write(data: Uint8Array): T;
+
+ size(): number {
+ return 4;
+ }
+
+ blockSize(): number {
+ return 1;
+ }
+
+ sum32(): number {
+ return this.#state;
+ }
+
+ sum(): Uint8Array {
+ return Uint8Array.from([
+ (this.#state >> 24) & 0xff,
+ (this.#state >> 16) & 0xff,
+ (this.#state >> 8) & 0xff,
+ this.#state & 0xff,
+ ]);
+ }
+}
+
+/** Fnv32 hash */
+export class Fnv32 extends Fnv32Base<Fnv32> {
+ write(data: Uint8Array): Fnv32 {
+ let hash = this.sum32();
+
+ data.forEach((c) => {
+ hash = mul32(hash, prime32);
+ hash ^= c;
+ });
+
+ this._updateState(hash);
+ return this;
+ }
+}
+
+/** Fnv32a hash */
+export class Fnv32a extends Fnv32Base<Fnv32a> {
+ write(data: Uint8Array): Fnv32a {
+ let hash = this.sum32();
+
+ data.forEach((c) => {
+ hash ^= c;
+ hash = mul32(hash, prime32);
+ });
+
+ this._updateState(hash);
+ return this;
+ }
+}
diff --git a/std/hash/_fnv/fnv64.ts b/std/hash/_fnv/fnv64.ts
new file mode 100644
index 000000000..8a5b5187d
--- /dev/null
+++ b/std/hash/_fnv/fnv64.ts
@@ -0,0 +1,89 @@
+// Ported from Go:
+// https://github.com/golang/go/tree/go1.13.10/src/hash/fnv/fnv.go
+// Copyright 2011 The Go Authors. All rights reserved. BSD license.
+// https://github.com/golang/go/blob/master/LICENSE
+// Copyright 2018-2020 the Deno authors. All rights reserved. MIT license.
+
+import { mul64 } from "./util.ts";
+
+const offset64Lo = 2216829733;
+const offset64Hi = 3421674724;
+const prime64Lo = 435;
+const prime64Hi = 256;
+
+abstract class Fnv64Base<T> {
+ #stateHi: number;
+ #stateLo: number;
+
+ constructor() {
+ this.#stateHi = offset64Hi;
+ this.#stateLo = offset64Lo;
+ }
+
+ protected _updateState([newStateHi, newStateLo]: [number, number]): void {
+ this.#stateHi = newStateHi;
+ this.#stateLo = newStateLo;
+ }
+
+ reset(): void {
+ this.#stateHi = offset64Hi;
+ this.#stateLo = offset64Lo;
+ }
+
+ abstract write(data: Uint8Array): T;
+
+ size(): number {
+ return 8;
+ }
+
+ blockSize(): number {
+ return 1;
+ }
+
+ sum64(): [number, number] {
+ return [this.#stateHi, this.#stateLo];
+ }
+
+ sum(): Uint8Array {
+ return Uint8Array.from([
+ (this.#stateHi >> 24) & 0xff,
+ (this.#stateHi >> 16) & 0xff,
+ (this.#stateHi >> 8) & 0xff,
+ this.#stateHi & 0xff,
+ (this.#stateLo >> 24) & 0xff,
+ (this.#stateLo >> 16) & 0xff,
+ (this.#stateLo >> 8) & 0xff,
+ this.#stateLo & 0xff,
+ ]);
+ }
+}
+
+/** Fnv64 hash */
+export class Fnv64 extends Fnv64Base<Fnv64> {
+ write(data: Uint8Array): Fnv64 {
+ let [hashHi, hashLo] = this.sum64();
+
+ data.forEach((c) => {
+ [hashHi, hashLo] = mul64([hashHi, hashLo], [prime64Hi, prime64Lo]);
+ hashLo ^= c;
+ });
+
+ this._updateState([hashHi, hashLo]);
+ return this;
+ }
+}
+
+/** Fnv64a hash */
+export class Fnv64a extends Fnv64Base<Fnv64a> {
+ write(data: Uint8Array): Fnv64 {
+ let [hashHi, hashLo] = this.sum64();
+
+ data.forEach((c) => {
+ hashLo ^= c;
+ [hashHi, hashLo] = mul64([hashHi, hashLo], [prime64Hi, prime64Lo]);
+ });
+
+ this._updateState([hashHi, hashLo]);
+ return this;
+ }
+}
diff --git a/std/hash/_fnv/util.ts b/std/hash/_fnv/util.ts
new file mode 100644
index 000000000..3d1cb5bac
--- /dev/null
+++ b/std/hash/_fnv/util.ts
@@ -0,0 +1,52 @@
+// Copyright 2018-2020 the Deno authors. All rights reserved. MIT license.
+
+function n16(n: number): number {
+ return n & 0xffff;
+}
+
+function n32(n: number): number {
+ return n >>> 0;
+}
+
+function add32WithCarry(a: number, b: number): [number, number] {
+ const added = n32(a) + n32(b);
+ return [n32(added), added > 0xffffffff ? 1 : 0];
+}
+
+function mul32WithCarry(a: number, b: number): [number, number] {
+ const al = n16(a);
+ const ah = n16(a >>> 16);
+ const bl = n16(b);
+ const bh = n16(b >>> 16);
+
+ const [t, tc] = add32WithCarry(al * bh, ah * bl);
+ const [n, nc] = add32WithCarry(al * bl, n32(t << 16));
+ const carry = nc + (tc << 16) + n16(t >>> 16) + ah * bh;
+
+ return [n, carry];
+}
+
+/**
+ * mul32 performs 32-bit multiplication, a * b
+ * @param a
+ * @param b
+ */
+export function mul32(a: number, b: number): number {
+ // https://stackoverflow.com/a/28151933
+ const al = n16(a);
+ const ah = a - al;
+ return n32(n32(ah * b) + al * b);
+}
+
+/**
+ * mul64 performs 64-bit multiplication with two 32-bit words
+ * @param [ah, al]
+ * @param [bh, bl]
+ */
+export function mul64(
+ [ah, al]: [number, number],
+ [bh, bl]: [number, number]
+): [number, number] {
+ const [n, c] = mul32WithCarry(al, bl);
+ return [n32(mul32(al, bh) + mul32(ah, bl) + c), n];
+}
diff --git a/std/hash/_fnv/util_test.ts b/std/hash/_fnv/util_test.ts
new file mode 100644
index 000000000..3b16d83cb
--- /dev/null
+++ b/std/hash/_fnv/util_test.ts
@@ -0,0 +1,71 @@
+// Copyright 2018-2020 the Deno authors. All rights reserved. MIT license.
+
+const { test } = Deno;
+import { assertEquals } from "../../testing/asserts.ts";
+import { mul32, mul64 } from "./util.ts";
+
+test("[hash/fnv/util] mul32", () => {
+ assertEquals(mul32(0xffffffff, 0xffffffff), 1);
+ assertEquals(mul32(0x12345678, 0xdeadbeef), 0x5621ca08);
+ assertEquals(mul32(0xf626f430, 0xff7469f1), 0x2a939130);
+ assertEquals(mul32(0x543f9412, 0x8a4aa84f), 0x39fe818e);
+ assertEquals(mul32(0x8ee170d1, 0x2fbbb9ec), 0x6a0609ac);
+ assertEquals(mul32(0xea3b3a14, 0xa397bd0a), 0xddfd08c8);
+ assertEquals(mul32(0x93f8536b, 0xa79e3c04), 0xcc7861ac);
+ assertEquals(mul32(0xf97dab98, 0xed526241), 0x2348c198);
+ assertEquals(mul32(0x35500191, 0xd5012447), 0xaff9d337);
+ assertEquals(mul32(0x471dde47, 0xaaa4950c), 0x4341be54);
+ assertEquals(mul32(0xd633970d, 0xa9bc2bcd), 0xb43b2469);
+ assertEquals(mul32(0xc60898cc, 0xbfe7dcc4), 0x15f84c30);
+});
+
+test("[hash/fnv/util] mul64", () => {
+ assertEquals(mul64([0xffffffff, 0xffffffff], [0xffffffff, 0xffffffff]), [
+ 0,
+ 1,
+ ]);
+ assertEquals(mul64([0x12345678, 0xdeadbeef], [0xcafebabe, 0xbaadf00d]), [
+ 0xc801c86b,
+ 0xdf55c223,
+ ]);
+ assertEquals(mul64([0xdc479aed, 0x24bc71a3], [0x543717c1, 0x4b6056b9]), [
+ 0x56c7ec8f,
+ 0x387ae0cb,
+ ]);
+ assertEquals(mul64([0xb84936ae, 0xb84becd2], [0x2864edd1, 0x14ee13cc]), [
+ 0xd87e9171,
+ 0x12504d58,
+ ]);
+ assertEquals(mul64([0xb0b73e95, 0x3f5cc701], [0x6c7b30b8, 0xcd7f0f9e]), [
+ 0x570551ee,
+ 0x116ae19e,
+ ]);
+ assertEquals(mul64([0xc237b433, 0x160b50bf], [0x3f937c23, 0xf26175f7]), [
+ 0x48a1d118,
+ 0x97313349,
+ ]);
+ assertEquals(mul64([0x386242fd, 0x6baa0fc0], [0xf81f7e23, 0xbe172381]), [
+ 0x4799f2a3,
+ 0x6b192fc0,
+ ]);
+ assertEquals(mul64([0x5afc8714, 0x902180d1], [0xa7068c96, 0xb859bb4d]), [
+ 0xb4589d29,
+ 0xd3d569dd,
+ ]);
+ assertEquals(mul64([0xb4e86a68, 0x619bee92], [0xd67560fa, 0x736982a7]), [
+ 0x72c73b5d,
+ 0x4bc0c53e,
+ ]);
+ assertEquals(mul64([0xfc8b5561, 0xbf91d6d5], [0x2bcb029a, 0xa144ead3]), [
+ 0x2da439a7,
+ 0x3926c38f,
+ ]);
+ assertEquals(mul64([0x47b62fae, 0xffe8cb4c], [0xbda77111, 0x6cad4968]), [
+ 0x9d9b7832,
+ 0xcae742e0,
+ ]);
+ assertEquals(mul64([0xc9160fc1, 0xd96e085b], [0x3adfd031, 0x3f75e557]), [
+ 0xe4d0bf23,
+ 0x88753ded,
+ ]);
+});
diff --git a/std/hash/fnv.ts b/std/hash/fnv.ts
new file mode 100644
index 000000000..ecabd4239
--- /dev/null
+++ b/std/hash/fnv.ts
@@ -0,0 +1,4 @@
+// Copyright 2018-2020 the Deno authors. All rights reserved. MIT license.
+
+export { Fnv32, Fnv32a } from "./_fnv/fnv32.ts";
+export { Fnv64, Fnv64a } from "./_fnv/fnv64.ts";
diff --git a/std/hash/fnv_test.ts b/std/hash/fnv_test.ts
new file mode 100644
index 000000000..6c2d66f9a
--- /dev/null
+++ b/std/hash/fnv_test.ts
@@ -0,0 +1,113 @@
+// Ported from Go:
+// https://github.com/golang/go/tree/go1.13.10/src/hash/fnv/fnv_test.go
+// Copyright 2011 The Go Authors. All rights reserved. BSD license.
+// https://github.com/golang/go/blob/master/LICENSE
+// Copyright 2018-2020 the Deno authors. All rights reserved. MIT license.
+
+const { test } = Deno;
+import { assertEquals } from "../testing/asserts.ts";
+import { Fnv32, Fnv32a, Fnv64, Fnv64a } from "./fnv.ts";
+
+const golden32 = [
+ ["", [0x81, 0x1c, 0x9d, 0xc5]],
+ ["a", [0x05, 0x0c, 0x5d, 0x7e]],
+ ["ab", [0x70, 0x77, 0x2d, 0x38]],
+ ["abc", [0x43, 0x9c, 0x2f, 0x4b]],
+ ["deno", [0x6e, 0xd5, 0xa7, 0xa9]],
+];
+
+const golden32a = [
+ ["", [0x81, 0x1c, 0x9d, 0xc5]],
+ ["a", [0xe4, 0x0c, 0x29, 0x2c]],
+ ["ab", [0x4d, 0x25, 0x05, 0xca]],
+ ["abc", [0x1a, 0x47, 0xe9, 0x0b]],
+ ["deno", [0x8e, 0xf6, 0x47, 0x11]],
+];
+
+const golden64 = [
+ ["", [0xcb, 0xf2, 0x9c, 0xe4, 0x84, 0x22, 0x23, 0x25]],
+ ["a", [0xaf, 0x63, 0xbd, 0x4c, 0x86, 0x01, 0xb7, 0xbe]],
+ ["ab", [0x08, 0x32, 0x67, 0x07, 0xb4, 0xeb, 0x37, 0xb8]],
+ ["abc", [0xd8, 0xdc, 0xca, 0x18, 0x6b, 0xaf, 0xad, 0xcb]],
+ ["deno", [0x14, 0xed, 0xb2, 0x7e, 0xec, 0xda, 0xad, 0xc9]],
+];
+
+const golden64a = [
+ ["", [0xcb, 0xf2, 0x9c, 0xe4, 0x84, 0x22, 0x23, 0x25]],
+ ["a", [0xaf, 0x63, 0xdc, 0x4c, 0x86, 0x01, 0xec, 0x8c]],
+ ["ab", [0x08, 0x9c, 0x44, 0x07, 0xb5, 0x45, 0x98, 0x6a]],
+ ["abc", [0xe7, 0x1f, 0xa2, 0x19, 0x05, 0x41, 0x57, 0x4b]],
+ ["deno", [0xa5, 0xd9, 0xfb, 0x67, 0x42, 0x6e, 0x48, 0xb1]],
+];
+
+test("[hash/fnv] testFnv32", () => {
+ for (const [input, output] of golden32) {
+ const fnv = new Fnv32();
+ fnv.write(new TextEncoder().encode(input as string));
+ assertEquals(fnv.sum(), output);
+ }
+});
+
+test("[hash/fnv] testFnv32a", () => {
+ for (const [input, output] of golden32a) {
+ const fnv = new Fnv32a();
+ fnv.write(new TextEncoder().encode(input as string));
+ assertEquals(fnv.sum(), output);
+ }
+});
+
+test("[hash/fnv] testFnv64", () => {
+ for (const [input, output] of golden64) {
+ const fnv = new Fnv64();
+ fnv.write(new TextEncoder().encode(input as string));
+ assertEquals(fnv.sum(), output);
+ }
+});
+
+test("[hash/fnv] testFnv64a", () => {
+ for (const [input, output] of golden64a) {
+ const fnv = new Fnv64a();
+ fnv.write(new TextEncoder().encode(input as string));
+ assertEquals(fnv.sum(), output);
+ }
+});
+
+test("[hash/fnv] testFnv32WriteChain", () => {
+ const fnv = new Fnv32();
+ fnv
+ .write(new TextEncoder().encode("d"))
+ .write(new TextEncoder().encode("e"))
+ .write(new TextEncoder().encode("n"))
+ .write(new TextEncoder().encode("o"));
+ assertEquals(fnv.sum(), [0x6e, 0xd5, 0xa7, 0xa9]);
+});
+
+test("[hash/fnv] testFnv32aWriteChain", () => {
+ const fnv = new Fnv32a();
+ fnv
+ .write(new TextEncoder().encode("d"))
+ .write(new TextEncoder().encode("e"))
+ .write(new TextEncoder().encode("n"))
+ .write(new TextEncoder().encode("o"));
+ assertEquals(fnv.sum(), [0x8e, 0xf6, 0x47, 0x11]);
+});
+
+test("[hash/fnv] testFnv64WriteChain", () => {
+ const fnv = new Fnv64();
+ fnv
+ .write(new TextEncoder().encode("d"))
+ .write(new TextEncoder().encode("e"))
+ .write(new TextEncoder().encode("n"))
+ .write(new TextEncoder().encode("o"));
+ assertEquals(fnv.sum(), [0x14, 0xed, 0xb2, 0x7e, 0xec, 0xda, 0xad, 0xc9]);
+});
+
+test("[hash/fnv] testFnv64aWriteChain", () => {
+ const fnv = new Fnv64a();
+ fnv
+ .write(new TextEncoder().encode("d"))
+ .write(new TextEncoder().encode("e"))
+ .write(new TextEncoder().encode("n"))
+ .write(new TextEncoder().encode("o"));
+ assertEquals(fnv.sum(), [0xa5, 0xd9, 0xfb, 0x67, 0x42, 0x6e, 0x48, 0xb1]);
+});
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-17 13:01:40 +0000