@ot-builder/bin-util - npm Package Compare versions

Comparing version 1.3.2 to 1.3.3

CHANGELOG.json

@@ -5,3 +5,36 @@ {
     {
-      "date": "Sat, 11 Dec 2021 01:08:14 GMT",
+      "date": "Sat, 18 Dec 2021 01:17:28 GMT",
+      "tag": "@ot-builder/bin-util_v1.3.3",
+      "version": "1.3.3",
+      "comments": {
+        "patch": [
+          {
+            "author": "[e-mail]",
+            "package": "@ot-builder/bin-util",
+            "commit": "df0486c2b6942815176c652a3150870ba8eacc71",
+            "comment": "Optimize frag unifier"
+          },
+          {
+            "author": "beachball",
+            "package": "@ot-builder/bin-util",
+            "comment": "Bump @ot-builder/errors to v1.3.3",
+            "commit": "df0486c2b6942815176c652a3150870ba8eacc71"
+          },
+          {
+            "author": "beachball",
+            "package": "@ot-builder/bin-util",
+            "comment": "Bump @ot-builder/prelude to v1.3.3",
+            "commit": "df0486c2b6942815176c652a3150870ba8eacc71"
+          },
+          {
+            "author": "beachball",
+            "package": "@ot-builder/bin-util",
+            "comment": "Bump @ot-builder/common-impl to v1.3.3",
+            "commit": "df0486c2b6942815176c652a3150870ba8eacc71"
+          }
+        ]
+      }
+    },
+    {
+      "date": "Sat, 11 Dec 2021 01:10:33 GMT",
       "tag": "@ot-builder/bin-util_v1.3.2",
@@ -8,0 +41,0 @@ "version": "1.3.2",

CHANGELOG.md

 # Change Log - @ot-builder/bin-util
 
-This log was last generated on Sat, 11 Dec 2021 01:08:14 GMT and should not be manually modified.
+This log was last generated on Sat, 18 Dec 2021 01:17:28 GMT and should not be manually modified.
 
 <!-- Start content -->
 
+## 1.3.3
+
+Sat, 18 Dec 2021 01:17:28 GMT
+
+### Patches
+
+- Optimize frag unifier ([e-mail])
+- Bump @ot-builder/errors to v1.3.3
+- Bump @ot-builder/prelude to v1.3.3
+- Bump @ot-builder/common-impl to v1.3.3
+
 ## 1.3.2
 
-Sat, 11 Dec 2021 01:08:14 GMT
+Sat, 11 Dec 2021 01:10:33 GMT
 
@@ -11,0 +22,0 @@ ### Patches

lib/handlers/fragment.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
 exports.Frag = exports.FragPointerEmbedding = exports.WriteOpt = exports.Write = void 0;
-const crypto = require("crypto");
+const Crypto = require("crypto");
+const ImpLib = require("@ot-builder/common-impl");
 const errors_1 = require("@ot-builder/errors");
@@ -31,20 +32,2 @@ const buffer_writer_1 = require("./buffer-writer");
 })(FragPointerEmbedding = exports.FragPointerEmbedding || (exports.FragPointerEmbedding = {}));
-class FragHashSink {
-    constructor() {
-        this.forward = new Map();
-        this.reward = new Map();
-    }
-    resolve(frag) {
-        const hash = this.forward.get(frag);
-        if (!hash)
-            return frag;
-        else
-            return this.reward.get(hash) || frag;
-    }
-    add(frag, hash) {
-        this.forward.set(frag, hash);
-        if (!this.reward.has(hash))
-            this.reward.set(hash, frag);
-    }
-}
 class Frag {
@@ -265,25 +248,94 @@ constructor() {
 }
-class Packing {
-    hash(frag, sink) {
-        const h = crypto.createHash("sha256");
-        h.update(frag.getDataBuffer());
+class Unifier {
+    constructor() {
+        this.hashCache = new WeakMap();
+        this.hashToFragMap = new Map();
+        this.unifyCache = new WeakMap();
+    }
+    hash(frag) {
+        const cached = this.hashCache.get(frag);
+        if (cached)
+            return cached;
+        const hr = new ImpLib.Hasher();
+        hr.buffer(frag.getDataBuffer());
         for (const ptr of frag.pointers) {
-            const targetHash = ptr.to ? this.hash(ptr.to, sink) : "NULL";
-            h.update(`{${ptr.size},${ptr.offset},${ptr.createdOffset},${ptr.embedding.id},${targetHash}}`);
+            const targetHash = ptr.to ? this.hash(ptr.to) : "NULL";
+            hr.string(targetHash);
+            hr.integer(ptr.size, ptr.offset, ptr.createdOffset);
+            hr.string(ptr.embedding.id);
         }
+        const h = Crypto.createHash("sha256");
+        hr.transfer(h);
         const result = h.digest("hex");
-        sink.add(frag, result);
+        this.hashCache.set(frag, result);
         return result;
     }
-    shareBlocks(root) {
-        const sink = new FragHashSink();
-        this.hash(root, sink);
-        for (const frag of sink.forward.keys()) {
-            for (const ptr of frag.pointers) {
-                if (!ptr.to)
-                    continue;
-                ptr.to = sink.resolve(ptr.to);
+    compare(a, b) {
+        if (!a) {
+            return !b;
+        }
+        else if (!b) {
+            return false;
+        }
+        else {
+            if (a === b)
+                return true;
+            if (this.hash(a) !== this.hash(b))
+                return false;
+            return this.compareByContents(a, b);
+        }
+    }
+    compareByContents(a, b) {
+        if (Buffer.compare(a.getDataBuffer(), b.getDataBuffer()) !== 0)
+            return false;
+        if (a.pointers.length !== b.pointers.length)
+            return false;
+        for (let index = 0; index < a.pointers.length; index++) {
+            const p1 = a.pointers[index], p2 = b.pointers[index];
+            if (p1.size !== p2.size)
+                return false;
+            if (p1.offset !== p2.offset)
+                return false;
+            if (p1.embedding.id !== p2.embedding.id)
+                return false;
+            if (p1.createdOffset !== p2.createdOffset)
+                return false;
+            if (!this.compare(p1.to, p2.to))
+                return false;
+        }
+        return true;
+    }
+    unify(frag) {
+        const cached = this.unifyCache.get(frag);
+        if (cached)
+            return cached;
+        // Unify sub-pointers
+        for (const ptr of frag.pointers) {
+            if (ptr.to)
+                ptr.to = this.unify(ptr.to);
+        }
+        const h = this.hash(frag);
+        let matches = this.hashToFragMap.get(h);
+        if (!matches) {
+            matches = [];
+            this.hashToFragMap.set(h, matches);
+        }
+        for (const candidate of matches) {
+            if (this.compare(frag, candidate)) {
+                return this.cacheUnification(frag, candidate, h, matches);
             }
         }
+        return this.cacheUnification(frag, frag, h, matches);
     }
+    cacheUnification(frag, unifiedTo, hash, hashSink) {
+        this.unifyCache.set(frag, unifiedTo);
+        hashSink.push(unifiedTo);
+        return unifiedTo;
+    }
+}
+class Packing {
+    shareBlocks(root) {
+        const sink = new Unifier();
+        sink.unify(root);
+    }
     allocateOffsets(root) {
@@ -290,0 +342,0 @@ const sorted = new Sorter().sort(root);

package.json

 {
   "name": "@ot-builder/bin-util",
   "description": "",
-  "version": "1.3.2",
+  "version": "1.3.3",
   "license": "MIT",
@@ -27,4 +27,5 @@ "repository": {
   "dependencies": {
-    "@ot-builder/errors": "1.3.2",
-    "@ot-builder/prelude": "1.3.2",
+    "@ot-builder/errors": "1.3.3",
+    "@ot-builder/prelude": "1.3.3",
+    "@ot-builder/common-impl": "1.3.3",
     "tslib": "^2.0.0"
@@ -31,0 +32,0 @@ },

No alert changes

Improved metrics

Total package byte prevSize

42864

7.88%

Lines of code

1207

7.58%

Worsened metrics

Dependency count

4

33.33%

Dependency changes

• + Added

  @ot-builder/common-impl@1.3.3

• + Added

  @ot-builder/common-impl@1.3.3
  (transitive)

• + Added

  @ot-builder/errors@1.3.3
  (transitive)

• + Added

  @ot-builder/prelude@1.3.3
  (transitive)

• - Removed

  @ot-builder/errors@1.3.2
  (transitive)

• - Removed

  @ot-builder/prelude@1.3.2
  (transitive)

• Updated

  @ot-builder/errors@1.3.3

• Updated

  @ot-builder/prelude@1.3.3