kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

blob.c (4366B)

      1 #include "blob.h"
      2 
      3 #include <string.h>
      4 
      5 #include "blake2b.h"
      6 
      7 static void put_u64le(uint8_t* p, uint64_t v) {
      8   unsigned i;
      9   for (i = 0; i < 8u; ++i) p[i] = (uint8_t)(v >> (8u * i));
     10 }
     11 
     12 static void hash_u64(DistBlake2b* h, uint64_t v) {
     13   uint8_t b[8];
     14   put_u64le(b, v);
     15   dist_blake2b_update(h, b, sizeof b);
     16 }
     17 
     18 void dist_blob_id(uint8_t out[DIST_BLAKE2B_LEN], const uint8_t* data,
     19                   size_t len) {
     20   /* The flat blob id is plain BLAKE2b of the bytes: it doubles as the CAS
     21    * content id and the package format's tree-object hash (pkg_hash), so it
     22    * must stay un-prefixed. (Domain separation from tree ids was considered
     23    * but would require coordinated changes across the whole .kpkg/CAS format.)
     24    */
     25   dist_blake2b(out, data, len);
     26 }
     27 
     28 void dist_blob_leaf_hash(uint8_t out[DIST_BLAKE2B_LEN], uint64_t chunk_index,
     29                          const uint8_t* raw, size_t raw_len) {
     30   static const uint8_t dom[] = "kit blob leaf v1";
     31   DistBlake2b h;
     32   dist_blake2b_init(&h, DIST_BLAKE2B_LEN);
     33   dist_blake2b_update(&h, dom, sizeof dom - 1u);
     34   hash_u64(&h, chunk_index);
     35   hash_u64(&h, (uint64_t)raw_len);
     36   dist_blake2b_update(&h, raw, raw_len);
     37   dist_blake2b_final(&h, out);
     38 }
     39 
     40 void dist_blob_node_hash(uint8_t out[DIST_BLAKE2B_LEN],
     41                          const uint8_t left[DIST_BLAKE2B_LEN],
     42                          const uint8_t right[DIST_BLAKE2B_LEN]) {
     43   static const uint8_t dom[] = "kit blob node v1";
     44   DistBlake2b h;
     45   dist_blake2b_init(&h, DIST_BLAKE2B_LEN);
     46   dist_blake2b_update(&h, dom, sizeof dom - 1u);
     47   dist_blake2b_update(&h, left, DIST_BLAKE2B_LEN);
     48   dist_blake2b_update(&h, right, DIST_BLAKE2B_LEN);
     49   dist_blake2b_final(&h, out);
     50 }
     51 
     52 void dist_blob_empty_root(uint8_t out[DIST_BLAKE2B_LEN]) {
     53   static const uint8_t dom[] = "kit blob empty v1";
     54   dist_blake2b(out, dom, sizeof dom - 1u);
     55 }
     56 
     57 int dist_blob_root(uint8_t out[DIST_BLAKE2B_LEN], const uint8_t* data,
     58                    size_t len, size_t chunk_size) {
     59   /* Bounded-memory Merkle root. This is bit-identical to a level-by-level
     60    * pairing that promotes a lone odd node, but computed in O(1) space: process
     61    * leaves left-to-right keeping a stack of completed perfect-subtree roots
     62    * (one per height), combining equal-height neighbours as they appear, then
     63    * fold the residual peaks left-to-right. A 64-entry stack covers any file up
     64    * to 2^64 leaves, so there is no longer a per-blob size cap. */
     65   uint8_t peaks[64][DIST_BLAKE2B_LEN];
     66   uint8_t height[64];
     67   size_t np = 0, leaves, i;
     68   if (chunk_size == 0) return DIST_ERR;
     69   if (len && !data) return DIST_ERR;
     70   if (len == 0) {
     71     dist_blob_empty_root(out);
     72     return DIST_OK;
     73   }
     74   leaves = (len + chunk_size - 1u) / chunk_size;
     75   for (i = 0; i < leaves; ++i) {
     76     size_t off = i * chunk_size;
     77     size_t n = len - off;
     78     if (n > chunk_size) n = chunk_size;
     79     dist_blob_leaf_hash(peaks[np], (uint64_t)i, data + off, n);
     80     height[np] = 0;
     81     ++np;
     82     /* Combine equal-height neighbours: builds the same perfect subtrees the
     83      * level-by-level pass would, left-to-right. */
     84     while (np >= 2u && height[np - 1u] == height[np - 2u]) {
     85       dist_blob_node_hash(peaks[np - 2u], peaks[np - 2u], peaks[np - 1u]);
     86       height[np - 2u] = (uint8_t)(height[np - 2u] + 1u);
     87       --np;
     88     }
     89   }
     90   /* Bag the residual peaks left-to-right: H(...H(H(p0,p1),p2)..., pk). This
     91    * matches the odd-node-promotion of the level algorithm. */
     92   while (np > 1u) {
     93     dist_blob_node_hash(peaks[0], peaks[0], peaks[1]);
     94     for (i = 1u; i + 1u < np; ++i)
     95       memcpy(peaks[i], peaks[i + 1u], DIST_BLAKE2B_LEN);
     96     --np;
     97   }
     98   {
     99     static const uint8_t dom[] = "kit blob root v1";
    100     DistBlake2b h;
    101     dist_blake2b_init(&h, DIST_BLAKE2B_LEN);
    102     dist_blake2b_update(&h, dom, sizeof dom - 1u);
    103     dist_blake2b_update(&h, peaks[0], DIST_BLAKE2B_LEN);
    104     dist_blake2b_final(&h, out);
    105   }
    106   return DIST_OK;
    107 }
    108 
    109 int dist_blob_info(DistBlobInfo* out, const uint8_t* data, size_t len,
    110                    size_t chunk_size) {
    111   if (!out || chunk_size == 0) return DIST_ERR;
    112   if (len && !data) return DIST_ERR;
    113   memset(out, 0, sizeof *out);
    114   dist_blob_id(out->id, data, len);
    115   if (dist_blob_root(out->root, data, len, chunk_size) != DIST_OK)
    116     return DIST_ERR;
    117   out->size = (uint64_t)len;
    118   out->chunks = len ? (uint64_t)((len + chunk_size - 1u) / chunk_size) : 0u;
    119   return DIST_OK;
    120 }