nx_palette.nx source

1// nx_palette.nx -- sub-byte voxel/pixel palette encoder. 2// 3// THE unlock primitive for Minecraft-equivalent on $5 ESP32-class 4// hardware. At 3 bits per voxel and an 8-color palette, a full 32x32x32 5// chunk fits in 12288 bytes (12 KiB). Pair with chunk paging from 6// flash and the entire walkable world streams within the working RAM 7// of an RP2040 / Cortex-M0+ class part. This is what makes a true 8// Minecraft demo on $5 of silicon feasible -- without sub-byte packing, 9// the same chunk needs 32 KiB minimum (one byte per voxel) which 10// blows past most MCU SRAM budgets. 11// 12// Composes: 13// nx_tier -- packing density scales naturally with NX_TIER_*; 14// MCU tier uses 1-3bpp, workstation tier may stay 15// at 8bpp for cache reasons 16// nx_budget -- the saved RAM bytes flow directly into the cell's 17// ram budget headroom 18// 19// V1 supports 1bpp (2-color), 2bpp (4-color), 3bpp (8-color), 4bpp 20// (16-color), and 8bpp pass-through. Bit-level packing is LSB-first 21// within each byte so unpack is a small shift + mask, friendly to 22// embedded targets without barrel shifters. 23// 24// Gap list (V1 honest perf verdict): 25// - no RLE compression on top of packing (queued for chunk save format) 26// - no dithering helper for 1bpp displays (caller's responsibility) 27// - palette index lookup not included (caller supplies palette) 28// - no SIMD unpack on workstation tier (scalar only) 29// - no compile-time-specialized variants per bpp (one function with 30// branch; per-bpp specialization queued behind benchmark gate) 31// 32// genealogy_id: classic_video_indexed_color + minecraft_chunk_format 33// lineage_id: substrate_palette_v1 34// 35// nx_safety_envelope: 36// intended_use: "Sub-byte palette index packing/unpacking for 37// memory-constrained voxel/pixel data" 38// sil_target: SIL1 39// evidence: [bit_alignment_correct, lossless_roundtrip, 40// bpp_validated_at_entry] 41// verdict: NOT_YET_EVALUATED 42 43import "nx_syscalls.nx" 44import "nx_tier.nx" 45 46// ===== Sealed enum: NxBpp ========================================= 47 48const NX_BPP_1: nx_int = 1 49const NX_BPP_2: nx_int = 2 50const NX_BPP_3: nx_int = 3 51const NX_BPP_4: nx_int = 4 52const NX_BPP_8: nx_int = 8 53 54// ===== Sealed enum: NxPaletteVerdict ============================= 55 56const NX_PAL_OK: nx_int = 0 57const NX_PAL_ERR_BAD_BPP: nx_int = 1 58const NX_PAL_ERR_BAD_INDEX: nx_int = 2 59 60// ===== nx_pal_bpp_is_valid ======================================= 61 62func nx_pal_bpp_is_valid(bpp: nx_int) -> nx_int { 63 if bpp == NX_BPP_1 { return 1 } 64 if bpp == NX_BPP_2 { return 1 } 65 if bpp == NX_BPP_3 { return 1 } 66 if bpp == NX_BPP_4 { return 1 } 67 if bpp == NX_BPP_8 { return 1 } 68 return 0 69} 70 71// ===== nx_pal_max_index ========================================== 72// 73// Maximum palette index storable at this bpp. Caller uses this to 74// validate that the source indices fit before packing. 75 76func nx_pal_max_index(bpp: nx_int) -> nx_int { 77 if bpp == NX_BPP_1 { return 1 } 78 if bpp == NX_BPP_2 { return 3 } 79 if bpp == NX_BPP_3 { return 7 } 80 if bpp == NX_BPP_4 { return 15 } 81 if bpp == NX_BPP_8 { return 255 } 82 return 0 83} 84 85// ===== nx_pal_packed_bytes ======================================= 86// 87// Bytes needed to store n_voxels indices at bpp. Rounds up so the 88// caller's allocation always covers the trailing partial byte. 89 90func nx_pal_packed_bytes(n_voxels: nx_size, bpp: nx_int) -> nx_size { 91 let total_bits: nx_size = n_voxels * (bpp as nx_size) 92 return (total_bits + 7) / 8 93} 94 95// ===== nx_palette_pack =========================================== 96// 97// Pack n_voxels palette indices from src (one index per byte, 0..255) 98// into dst (LSB-first within each byte). Returns NX_PAL_OK on success, 99// or NX_PAL_ERR_BAD_INDEX if any src index exceeds nx_pal_max_index(bpp). 100// dst must be at least nx_pal_packed_bytes(n_voxels, bpp) in size. 101 102func nx_palette_pack(src: *u8, n_voxels: nx_size, bpp: nx_int, dst: *u8) -> nx_int { 103 if nx_pal_bpp_is_valid(bpp) == 0 { return NX_PAL_ERR_BAD_BPP } 104 let max_idx: nx_int = nx_pal_max_index(bpp) 105 106 // Zero dst so OR-in bits compose cleanly. 107 let dst_bytes: nx_size = nx_pal_packed_bytes(n_voxels, bpp) 108 var z: nx_size = 0 109 while z < dst_bytes { 110 dst[z] = 0 111 z = z + 1 112 } 113 114 let bpp_s: nx_size = bpp as nx_size 115 var i: nx_size = 0 116 while i < n_voxels { 117 let idx_val: nx_int = (src[i] as i64) & 255 118 if idx_val > max_idx { return NX_PAL_ERR_BAD_INDEX } 119 let bit_off: nx_size = i * bpp_s 120 let byte_off: nx_size = bit_off / 8 121 let bit_in_byte: nx_size = bit_off - (byte_off * 8) 122 // Low bits go into current byte; spill bits (if any) into next. 123 let low_room: nx_size = 8 - bit_in_byte 124 if bpp_s <= low_room { 125 let cur: nx_int = (dst[byte_off] as i64) & 255 126 let placed: nx_int = (idx_val & 255) << bit_in_byte 127 dst[byte_off] = (cur | placed) as u8 128 } else { 129 let spill: nx_size = bpp_s - low_room 130 let low_mask: nx_int = (1 << low_room) - 1 131 let low_part: nx_int = idx_val & low_mask 132 let high_part: nx_int = (idx_val >> low_room) & ((1 << spill) - 1) 133 let cur0: nx_int = (dst[byte_off] as i64) & 255 134 dst[byte_off] = (cur0 | (low_part << bit_in_byte)) as u8 135 let cur1: nx_int = (dst[byte_off + 1] as i64) & 255 136 dst[byte_off + 1] = (cur1 | high_part) as u8 137 } 138 i = i + 1 139 } 140 return NX_PAL_OK 141} 142 143// ===== nx_palette_unpack ========================================= 144// 145// Inverse of pack. Reads n_voxels indices from src (LSB-first) and 146// writes them one-byte-per-index into dst. Caller-allocated dst must 147// have at least n_voxels bytes. 148 149func nx_palette_unpack(src: *u8, n_voxels: nx_size, bpp: nx_int, dst: *u8) -> nx_int { 150 if nx_pal_bpp_is_valid(bpp) == 0 { return NX_PAL_ERR_BAD_BPP } 151 let bpp_s: nx_size = bpp as nx_size 152 let mask: nx_int = (1 << bpp) - 1 153 154 var i: nx_size = 0 155 while i < n_voxels { 156 let bit_off: nx_size = i * bpp_s 157 let byte_off: nx_size = bit_off / 8 158 let bit_in_byte: nx_size = bit_off - (byte_off * 8) 159 let low_room: nx_size = 8 - bit_in_byte 160 var v: nx_int = 0 161 if bpp_s <= low_room { 162 let b: nx_int = (src[byte_off] as i64) & 255 163 v = (b >> bit_in_byte) & mask 164 } else { 165 let spill: nx_size = bpp_s - low_room 166 let b0: nx_int = (src[byte_off] as i64) & 255 167 let b1: nx_int = (src[byte_off + 1] as i64) & 255 168 let low_mask: nx_int = (1 << low_room) - 1 169 let low_part: nx_int = (b0 >> bit_in_byte) & low_mask 170 let high_part: nx_int = b1 & ((1 << spill) - 1) 171 v = low_part | (high_part << low_room) 172 } 173 dst[i] = (v & 255) as u8 174 i = i + 1 175 } 176 return NX_PAL_OK 177}