shadow_compress.go raw
1 package crypto
2
3 import (
4 "container/heap"
5 "errors"
6
7 "git.mleku.dev/mleku/dendrite/pkg/epoch"
8 "git.mleku.dev/mleku/dendrite/pkg/ratio"
9 "git.mleku.dev/mleku/dendrite/pkg/state"
10 )
11
12 // ShadowCompress compresses data using Huffman coding over hexagram
13 // tokens, with auxiliary data encoded in the S_3×S_3 permutation
14 // pair shadow channel.
15 //
16 // The primary stream is the Huffman-coded hexagram bitstream.
17 // The shadow stream encodes which of 36 possible permutation pairs
18 // was applied at each token position. The "home" pair (index 0) is
19 // determined by the epoch phase; deviations encode auxiliary bits.
20 //
21 // Shadow capacity: ~5 bits per hexagram token (log2(35) ≈ 5.1).
22 //
23 // Algorithm:
24 // 1. Convert data to hexagram tokens
25 // 2. Build frequency table and Huffman tree (exact rational weights)
26 // 3. For each token, select permutation pair based on auxiliary data
27 // 4. Huffman-encode the permuted tokens
28 // 5. Pack shadow stream (pair indices, 6 bits each)
29 func ShadowCompress(
30 data []byte,
31 auxiliary []byte,
32 ep epoch.Epoch,
33 ) (*ShadowCompressed, error) {
34 if len(data) == 0 {
35 return &ShadowCompressed{
36 OrigLen: 0,
37 EpochDec: ep.DecExp,
38 EpochBin: ep.BinExp,
39 ContentHash: Hash(nil),
40 }, nil
41 }
42
43 // 1. Hexagram encoding.
44 tokens := state.EncodeBytes(data)
45 tokenCount := len(tokens)
46
47 // 2. For each token, select permutation pair and apply shadow
48 // decomposition. This must happen before building the frequency
49 // table because Huffman coding operates on the permuted tokens.
50 auxBits := bytesToBits(auxiliary)
51 auxPos := 0
52
53 shadowIndices := make([]uint8, tokenCount)
54 permutedTokens := make([]state.Hexagram, tokenCount)
55
56 for i, tok := range tokens {
57 homeBin, homeDec := PhasePerms(ep, i)
58
59 // Determine how many auxiliary bits to encode at this position.
60 // We can encode up to 5 bits (values 1-35 map to 0-34 → 5 bits).
61 var pairIdx uint8
62 if auxPos < len(auxBits) {
63 // Extract up to 5 bits of auxiliary data.
64 val := uint8(0)
65 bits := 0
66 for bits < 5 && auxPos < len(auxBits) {
67 val |= auxBits[auxPos] << uint(bits)
68 auxPos++
69 bits++
70 }
71 // Pair index 0 = home pair (no auxiliary data).
72 // Pair indices 1-35 encode auxiliary values 0-34.
73 if val < 35 {
74 pairIdx = val + 1
75 } else {
76 pairIdx = 0 // overflow: use home pair
77 }
78 }
79
80 shadowIndices[i] = pairIdx
81
82 // Apply the selected permutation pair.
83 binP, decP := PairFromIndex(pairIdx, homeBin, homeDec)
84 permutedTokens[i] = ShadowDecompose(tok, binP, decP)
85 }
86
87 // 3. Build frequency table from permuted tokens.
88 var freq [64]uint32
89 for _, tok := range permutedTokens {
90 freq[tok&0x3F]++
91 }
92
93 // 4. Build Huffman tree with exact rational weights.
94 total := int64(tokenCount)
95 tree := buildHuffmanTree(freq, total)
96 codes := make(map[state.Hexagram]huffCode)
97 buildCodes(tree, nil, codes)
98
99 // 5. Huffman-encode the permuted tokens.
100 primary := huffmanEncode(permutedTokens, codes)
101
102 // 6. Pack shadow indices (6 bits each).
103 shadow := packShadowIndices(shadowIndices)
104
105 return &ShadowCompressed{
106 Primary: primary,
107 Shadow: shadow,
108 FreqTable: freq,
109 EpochDec: ep.DecExp,
110 EpochBin: ep.BinExp,
111 OrigLen: len(data),
112 TokenCount: tokenCount,
113 ShadowPayloadLen: len(auxiliary),
114 ContentHash: Hash(data),
115 }, nil
116 }
117
118 // ShadowDecompress recovers the original data and any embedded
119 // auxiliary payload from a shadow-compressed stream.
120 func ShadowDecompress(
121 sc *ShadowCompressed,
122 ep epoch.Epoch,
123 ) (data []byte, auxiliary []byte, err error) {
124 if sc == nil {
125 return nil, nil, errors.New("crypto: nil shadow compressed")
126 }
127 if sc.OrigLen == 0 {
128 return nil, nil, nil
129 }
130
131 // 1. Rebuild Huffman tree from frequency table.
132 total := int64(sc.TokenCount)
133 tree := buildHuffmanTree(sc.FreqTable, total)
134
135 // 2. Huffman-decode the primary stream to get permuted tokens.
136 permutedTokens := huffmanDecode(sc.Primary, tree, sc.TokenCount)
137
138 // 3. Unpack shadow indices.
139 shadowIndices := unpackShadowIndices(sc.Shadow, sc.TokenCount)
140
141 // 4. Recover original tokens and extract auxiliary bits.
142 tokens := make([]state.Hexagram, sc.TokenCount)
143 var auxBits []uint8
144 totalAuxBits := sc.ShadowPayloadLen * 8
145
146 for i, ptok := range permutedTokens {
147 homeBin, homeDec := PhasePerms(ep, i)
148 pairIdx := shadowIndices[i]
149
150 // Recover the permutation pair that was used.
151 binP, decP := PairFromIndex(pairIdx, homeBin, homeDec)
152
153 // Apply inverse permutation to recover original token.
154 tokens[i] = ShadowRecompose(ptok, binP, decP)
155
156 // Extract auxiliary bits from the pair index.
157 // Only extract as many bits as the compress side packed:
158 // the final group may have fewer than 5 bits.
159 if pairIdx > 0 {
160 val := pairIdx - 1
161 for b := range 5 {
162 if len(auxBits) >= totalAuxBits {
163 break
164 }
165 auxBits = append(auxBits, (val>>uint(b))&1)
166 }
167 }
168 }
169
170 // 5. Decode hexagrams to bytes.
171 data = state.DecodeHexagrams(tokens, sc.OrigLen)
172
173 // 6. Convert auxiliary bits back to bytes.
174 if sc.ShadowPayloadLen > 0 {
175 auxiliary = bitsToBytes(auxBits, sc.ShadowPayloadLen)
176 }
177
178 // 7. Verify content hash.
179 if Hash(data) != sc.ContentHash {
180 return nil, nil, errors.New("crypto: shadow decompression integrity check failed")
181 }
182
183 return data, auxiliary, nil
184 }
185
186 // huffCode stores the Huffman code for a symbol.
187 type huffCode struct {
188 bits []uint8 // sequence of 0/1 bits, MSB first
189 length int
190 }
191
192 // huffNode is a node in the Huffman tree with exact rational weights.
193 type huffNode struct {
194 symbol state.Hexagram
195 weight ratio.Ratio
196 left *huffNode
197 right *huffNode
198 leaf bool
199 }
200
201 // huffHeap implements heap.Interface for huffNode priority queue.
202 type huffHeap []*huffNode
203
204 func (h huffHeap) Len() int { return len(h) }
205 func (h huffHeap) Less(i, j int) bool { return h[i].weight.Less(h[j].weight) }
206 func (h huffHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
207 func (h *huffHeap) Push(x any) { *h = append(*h, x.(*huffNode)) }
208 func (h *huffHeap) Pop() any {
209 old := *h
210 n := len(old)
211 item := old[n-1]
212 *h = old[:n-1]
213 return item
214 }
215
216 // buildHuffmanTree constructs a Huffman tree from frequency counts
217 // using exact rational arithmetic for all weight comparisons.
218 func buildHuffmanTree(freq [64]uint32, total int64) *huffNode {
219 if total == 0 {
220 total = 1
221 }
222
223 h := &huffHeap{}
224 heap.Init(h)
225
226 for i := range 64 {
227 if freq[i] > 0 {
228 heap.Push(h, &huffNode{
229 symbol: state.Hexagram(i),
230 weight: ratio.New(int64(freq[i]), total),
231 leaf: true,
232 })
233 }
234 }
235
236 // Handle edge cases: 0 or 1 symbols.
237 if h.Len() == 0 {
238 return &huffNode{leaf: true, weight: ratio.Zero}
239 }
240 if h.Len() == 1 {
241 node := heap.Pop(h).(*huffNode)
242 return &huffNode{
243 weight: node.weight,
244 left: node,
245 leaf: false,
246 }
247 }
248
249 // Standard Huffman construction.
250 for h.Len() > 1 {
251 a := heap.Pop(h).(*huffNode)
252 b := heap.Pop(h).(*huffNode)
253 heap.Push(h, &huffNode{
254 weight: a.weight.Add(b.weight),
255 left: a,
256 right: b,
257 leaf: false,
258 })
259 }
260
261 return heap.Pop(h).(*huffNode)
262 }
263
264 // buildCodes recursively builds the codebook from the Huffman tree.
265 func buildCodes(node *huffNode, prefix []uint8, codes map[state.Hexagram]huffCode) {
266 if node == nil {
267 return
268 }
269 if node.leaf {
270 code := make([]uint8, len(prefix))
271 copy(code, prefix)
272 if len(code) == 0 {
273 code = []uint8{0} // single-symbol edge case
274 }
275 codes[node.symbol] = huffCode{bits: code, length: len(code)}
276 return
277 }
278 buildCodes(node.left, append(prefix, 0), codes)
279 buildCodes(node.right, append(prefix, 1), codes)
280 }
281
282 // huffmanEncode encodes a sequence of hexagram tokens using Huffman codes.
283 func huffmanEncode(tokens []state.Hexagram, codes map[state.Hexagram]huffCode) []byte {
284 var bits []uint8
285 for _, tok := range tokens {
286 code, ok := codes[tok]
287 if !ok {
288 // Token not in codebook — this can happen if the permuted
289 // token wasn't in the original frequency table. Use the
290 // identity code (longest possible).
291 for range 6 {
292 bits = append(bits, 0)
293 }
294 continue
295 }
296 bits = append(bits, code.bits...)
297 }
298 return bitsToBytesPacked(bits)
299 }
300
301 // huffmanDecode decodes a Huffman-coded bitstream back to hexagram tokens.
302 func huffmanDecode(data []byte, tree *huffNode, count int) []state.Hexagram {
303 if tree == nil || count == 0 {
304 return nil
305 }
306
307 bits := byteToBitsPacked(data)
308 tokens := make([]state.Hexagram, 0, count)
309 node := tree
310 for _, bit := range bits {
311 if len(tokens) >= count {
312 break
313 }
314 if bit == 0 {
315 node = node.left
316 } else {
317 node = node.right
318 }
319 if node == nil {
320 break
321 }
322 if node.leaf {
323 tokens = append(tokens, node.symbol)
324 node = tree
325 }
326 }
327 return tokens
328 }
329
330 // packShadowIndices packs 6-bit indices into a byte stream.
331 // Each index is 0-35, fitting in 6 bits.
332 func packShadowIndices(indices []uint8) []byte {
333 totalBits := len(indices) * 6
334 out := make([]byte, (totalBits+7)/8)
335 bitPos := 0
336 for _, idx := range indices {
337 for b := range 6 {
338 if idx&(1<<uint(b)) != 0 {
339 out[bitPos/8] |= 1 << uint(bitPos%8)
340 }
341 bitPos++
342 }
343 }
344 return out
345 }
346
347 // unpackShadowIndices unpacks 6-bit indices from a byte stream.
348 func unpackShadowIndices(data []byte, count int) []uint8 {
349 indices := make([]uint8, count)
350 bitPos := 0
351 for i := range count {
352 var val uint8
353 for b := range 6 {
354 byteIdx := bitPos / 8
355 bitIdx := uint(bitPos % 8)
356 if byteIdx < len(data) && data[byteIdx]&(1<<bitIdx) != 0 {
357 val |= 1 << uint(b)
358 }
359 bitPos++
360 }
361 indices[i] = val
362 }
363 return indices
364 }
365
366 // bytesToBits converts a byte slice to individual bits (LSB first per byte).
367 func bytesToBits(data []byte) []uint8 {
368 bits := make([]uint8, len(data)*8)
369 for i, b := range data {
370 for j := range 8 {
371 bits[i*8+j] = (b >> uint(j)) & 1
372 }
373 }
374 return bits
375 }
376
377 // bitsToBytes converts individual bits back to bytes (LSB first per byte).
378 func bitsToBytes(bits []uint8, length int) []byte {
379 out := make([]byte, length)
380 for i := range length {
381 var b byte
382 for j := range 8 {
383 idx := i*8 + j
384 if idx < len(bits) && bits[idx] != 0 {
385 b |= 1 << uint(j)
386 }
387 }
388 out[i] = b
389 }
390 return out
391 }
392
393 // bitsToBytesPacked packs a bit sequence into bytes (MSB first).
394 func bitsToBytesPacked(bits []uint8) []byte {
395 out := make([]byte, (len(bits)+7)/8)
396 for i, bit := range bits {
397 if bit != 0 {
398 out[i/8] |= 1 << uint(7-i%8)
399 }
400 }
401 return out
402 }
403
404 // byteToBitsPacked unpacks bytes into individual bits (MSB first).
405 func byteToBitsPacked(data []byte) []uint8 {
406 bits := make([]uint8, len(data)*8)
407 for i, b := range data {
408 for j := range 8 {
409 bits[i*8+j] = (b >> uint(7-j)) & 1
410 }
411 }
412 return bits
413 }
414