)]}'
{
  "commit": "5f6ecb0cf341d26ad24bf283c78cf6678ea17eba",
  "tree": "e8ed233f474926f3a0b6bed8e486e3c1a9b327f7",
  "parents": [
    "72fca0181a0621be6a26f59142d3959c6a13d4b4"
  ],
  "author": {
    "name": "Nico Weber",
    "email": "thakis@chromium.org",
    "time": "Mon Sep 14 17:02:33 2026 -0700"
  },
  "committer": {
    "name": "pdfium-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "email": "pdfium-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "time": "Mon Sep 14 17:02:33 2026 -0700"
  },
  "message": "Reduce JBIG2 Huffman reading work per bit from O(n) to O(1)\n\nDecodeAValue() repeatedly read one bit and then scanned the whole symbol\ntable to find a match.\n\nInstead, precompute for each code length how many codes there are with\nthis length, and have an index that orders symbols first by code length,\nand then by value.\n\nThis allows doing the per-bit work in O(1) time.\n\n(This is still less efficient than the usual efficient huffman decoding\nloop described e.g. in https://www.hanshq.net/zip.html#huffdec that\nusually reads all bits for a symbol in a single read, but it\u0027s enough of\na progression to push huffman work low in profiles.)\n\nTakes `pdfium_test Mellor_ACTITC_01.pdf --pages\u003d1-30` from 9.7s to 1.5s.\n\nChange on:\n\n    hyperfine \u0027pdfium_test --pages\u003d1-30 Mellor_ACTITC_01.pdf\u0027\n\nBefore:\n\n    Benchmark 1: pdfium_test --pages\u003d1-30 Mellor_ACTITC_01.pdf\n      Time (mean ± σ):     11.135 s ±  0.426 s    [User: 11.011 s, System: 0.117 s]\n      Range (min … max):   10.603 s … 11.800 s    10 runs\n\nAfter:\n\n    Benchmark 1: pdfium_test --pages\u003d1-30 Mellor_ACTITC_01.pdf\n      Time (mean ± σ):      1.255 s ±  0.005 s    [User: 1.170 s, System: 0.081 s]\n      Range (min … max):    1.247 s …  1.263 s    10 runs\n\n88.7% less time: the old code took 8.8x as long as the new code for this\nfile.\n\nRendering pages 20-22 of Mellor_ACTITC_11.pdf, with a local change to\nbump up limits to allow rendering it, goes from 8.6s to 0.91s. An even\nbigger speedup, because that file has a larger table, so the O(n) hurt\neven more.\n\nThe new test file in\nhttps://pdfium-review.googlesource.com/c/pdfium_tests/+/157510 with the\nsame local change to bump limits goes from 12.9s to 3.5s.\n\nAlso make a few variables and fields unsigned while here.\n\nNo intended behavior change.\n\nBug: 555145149\nChange-Id: I87cea0e76b7984698812ccd50f8e2c58b0c0ce02\nReviewed-on: https://pdfium-review.googlesource.com/c/pdfium/+/157550\nReviewed-by: Nico Weber \u003cthakis@google.com\u003e\nReviewed-by: Lei Zhang \u003cthestig@chromium.org\u003e\nCommit-Queue: Nico Weber \u003cthakis@chromium.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "3d2061d596fa7e31260b5e2176d8179409b8075e",
      "old_mode": 33188,
      "old_path": "core/fxcodec/jbig2/jbig2_huffman_decoder.cpp",
      "new_id": "65b81c471ff3ed3d7890f054dcd7f6b80b482209",
      "new_mode": 33188,
      "new_path": "core/fxcodec/jbig2/jbig2_huffman_decoder.cpp"
    },
    {
      "type": "modify",
      "old_id": "264c7ab7977e7425796d900ef4ecf34e953ff61a",
      "old_mode": 33188,
      "old_path": "core/fxcodec/jbig2/jbig2_huffman_table.cpp",
      "new_id": "e867a3874938196a6088887feadfc9374683d3dd",
      "new_mode": 33188,
      "new_path": "core/fxcodec/jbig2/jbig2_huffman_table.cpp"
    },
    {
      "type": "modify",
      "old_id": "47ddad1743c257cde8ed70e8443999bb7c0f8bda",
      "old_mode": 33188,
      "old_path": "core/fxcodec/jbig2/jbig2_huffman_table.h",
      "new_id": "07afded04fa75f690738d73f8a9f0e9b82c89020",
      "new_mode": 33188,
      "new_path": "core/fxcodec/jbig2/jbig2_huffman_table.h"
    }
  ]
}