summaryrefslogtreecommitdiff
path: root/std/hash/_fnv
diff options
context:
space:
mode:
Diffstat (limited to 'std/hash/_fnv')
-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.ts69
4 files changed, 0 insertions, 289 deletions
diff --git a/std/hash/_fnv/fnv32.ts b/std/hash/_fnv/fnv32.ts
deleted file mode 100644
index 679d44a62..000000000
--- a/std/hash/_fnv/fnv32.ts
+++ /dev/null
@@ -1,79 +0,0 @@
-// 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-2021 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
deleted file mode 100644
index 882636d0e..000000000
--- a/std/hash/_fnv/fnv64.ts
+++ /dev/null
@@ -1,89 +0,0 @@
-// 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-2021 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
deleted file mode 100644
index 8afed8e82..000000000
--- a/std/hash/_fnv/util.ts
+++ /dev/null
@@ -1,52 +0,0 @@
-// Copyright 2018-2021 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
deleted file mode 100644
index fb9dd3208..000000000
--- a/std/hash/_fnv/util_test.ts
+++ /dev/null
@@ -1,69 +0,0 @@
-// Copyright 2018-2021 the Deno authors. All rights reserved. MIT license.
-import { assertEquals } from "../../testing/asserts.ts";
-import { mul32, mul64 } from "./util.ts";
-
-Deno.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);
-});
-
-Deno.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,
- ]);
-});
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-03 01:36:22 +0000