Commit eb339b7c for libheif

commit eb339b7c4a296806b589cf01d4ff1780f926596d
Author: Dirk Farin <dirk.farin@gmail.com>
Date:   Sat Sep 5 00:56:12 2026 +0200

    Index Box_iref references by from_item_ID (GHSA-vg7w-rp49-4fc2)

    The three iref query methods (has_references, get_references_from,
    get_references) each scanned the full m_references vector, so resolving
    references for N items over an iref box with M entries cost O(N*M). With
    many items and a large iref box this was the residual quadratic left
    after the iinf item cap.

    Add an unordered_map from from_item_ID to the positions in m_references
    and route all three queries through it, reducing the total cost to
    O(N + M). The index is maintained incrementally: parse() builds it,
    add_references() appends, and overwrite_reference() needs no update
    because it only edits to_item_ID. Reference order within a from_item_ID
    is preserved, so get_references still returns the first (id, type) match.

    On a file with 1000 items and 160000 dimg references, read time drops
    from 1.83s to 0.26s.

    Part of GHSA-vg7w-rp49-4fc2.

diff --git a/libheif/box.cc b/libheif/box.cc
index 33ad24d4..ebb16093 100644
--- a/libheif/box.cc
+++ b/libheif/box.cc
@@ -4082,6 +4082,8 @@ Error Box_iref::parse(BitstreamRange& range, const heif_security_limits* limits)
   }
 #endif

+  build_index();
+
   return range.get_error();
 }

@@ -4178,15 +4180,25 @@ std::string Box_iref::dump(Indent& indent) const
 }


-bool Box_iref::has_references(uint32_t itemID) const
+void Box_iref::build_index()
 {
-  for (const Reference& ref : m_references) {
-    if (ref.from_item_ID == itemID) {
-      return true;
-    }
+  m_from_id_index.clear();
+  m_from_id_index.reserve(m_references.size());
+  for (size_t i = 0; i < m_references.size(); i++) {
+    add_to_index(i);
   }
+}

-  return false;
+
+void Box_iref::add_to_index(size_t reference_index)
+{
+  m_from_id_index[m_references[reference_index].from_item_ID].push_back(reference_index);
+}
+
+
+bool Box_iref::has_references(uint32_t itemID) const
+{
+  return m_from_id_index.find(itemID) != m_from_id_index.end();
 }


@@ -4194,9 +4206,11 @@ std::vector<Box_iref::Reference> Box_iref::get_references_from(heif_item_id item
 {
   std::vector<Reference> references;

-  for (const Reference& ref : m_references) {
-    if (ref.from_item_ID == itemID) {
-      references.push_back(ref);
+  auto iter = m_from_id_index.find(itemID);
+  if (iter != m_from_id_index.end()) {
+    references.reserve(iter->second.size());
+    for (size_t ref_idx : iter->second) {
+      references.push_back(m_references[ref_idx]);
     }
   }

@@ -4206,10 +4220,13 @@ std::vector<Box_iref::Reference> Box_iref::get_references_from(heif_item_id item

 std::vector<uint32_t> Box_iref::get_references(uint32_t itemID, uint32_t ref_type) const
 {
-  for (const Reference& ref : m_references) {
-    if (ref.from_item_ID == itemID &&
-        ref.header.get_short_type() == ref_type) {
-      return ref.to_item_ID;
+  auto iter = m_from_id_index.find(itemID);
+  if (iter != m_from_id_index.end()) {
+    for (size_t ref_idx : iter->second) {
+      const Reference& ref = m_references[ref_idx];
+      if (ref.header.get_short_type() == ref_type) {
+        return ref.to_item_ID;
+      }
     }
   }

@@ -4227,6 +4244,7 @@ void Box_iref::add_references(heif_item_id from_id, uint32_t type, const std::ve
   assert(to_ids.size() <= 0xFFFF);

   m_references.push_back(ref);
+  add_to_index(m_references.size() - 1);
 }


diff --git a/libheif/box.h b/libheif/box.h
index f3b099bb..30663a06 100644
--- a/libheif/box.h
+++ b/libheif/box.h
@@ -32,6 +32,7 @@

 #include <utility>
 #include <vector>
+#include <unordered_map>
 #include <string>
 #include <memory>
 #include <limits>
@@ -1098,6 +1099,17 @@ protected:

 private:
   std::vector<Reference> m_references;
+
+  // Index from 'from_item_ID' to the positions in m_references, so the
+  // reference queries run in O(matches) instead of O(m_references). It is kept
+  // in sync incrementally: parse() builds it, add_references() appends to it,
+  // and overwrite_reference() leaves it untouched (it only edits to_item_ID,
+  // not from_item_ID).
+  std::unordered_map<heif_item_id, std::vector<size_t>> m_from_id_index;
+
+  void build_index();
+
+  void add_to_index(size_t reference_index);
 };