From ae44478b30d890fe0fb04022f44d474dcdcc3f9d Mon Sep 17 00:00:00 2001 From: Lassi Pulkkinen Date: Thu, 31 Oct 2024 03:11:21 +0200 Subject: Initial commit (import old repo) --- comparray/+test.ha | 52 +++++++++++++ comparray/array.ha | 210 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 262 insertions(+) create mode 100644 comparray/+test.ha create mode 100644 comparray/array.ha (limited to 'comparray') diff --git a/comparray/+test.ha b/comparray/+test.ha new file mode 100644 index 0000000..df257d3 --- /dev/null +++ b/comparray/+test.ha @@ -0,0 +1,52 @@ +use bufio; +use fmt; +use math::random; +use os; + +@test fn struct_size() void = { + assert(size(Array) == 3 * size(*opaque)); +}; + +const TEST_SIZES: [_]u8 = [ + CONSTANT, 2, 3, 4, 5, 6, 7, 8, 16, 17, 32, 33, 100, 200, 255, + DIRECT, +]; +const TEST_ARRAYLEN: size = 4096; + +@test fn consistency() void = { + let rng = random::init(42); + + for (let i = 0z; i < len(TEST_SIZES); i += 1) { + for (let j = i + 1; j < len(TEST_SIZES); j += 1) { + fmt::printf("{},{} ", TEST_SIZES[i], TEST_SIZES[j])!; + + let array = new(TEST_SIZES[i], TEST_ARRAYLEN); + defer clear(&array, 0); + + let palette = get_palette(&array); + + for (let k = 0z; k < TEST_SIZES[i]; k += 1) { + palette[k] = random::next(&rng): u16; + }; + + let unpacked: []u16 = alloc([], TEST_ARRAYLEN); + defer free(unpacked); + + for (let k = 0z; k < TEST_ARRAYLEN; k += 1) { + const ref = + random::u32n(&rng, TEST_SIZES[i]): u8; + static append(unpacked, palette[ref]); + set(&array, k, ref); + }; + + grow_palette(&array, TEST_ARRAYLEN, TEST_SIZES[j]); + + for (let k = 0z; k < TEST_ARRAYLEN; k += 1) { + assert( + lookup(&array, get(&array, k)) + == unpacked[k] + ); + }; + }; + }; +}; diff --git a/comparray/array.ha b/comparray/array.ha new file mode 100644 index 0000000..6fa90e9 --- /dev/null +++ b/comparray/array.ha @@ -0,0 +1,210 @@ +use math; +use types; + +// premature optimization ftw! + +export def DIRECT: u8 = 0; +export def CONSTANT: u8 = 1; +export def INLINE_MAX: u8 = ((size(*opaque) * 2 - 1) / 2): u8; + +export type Array = union { + // (2024 note): this used to use duplicate struct member names, which i guess + // was a compiler bug and doesn't work anymore. + struct { // direct + palette_size: u8, // == DIRECT + data_direct: *[*]u16, + }, + struct { // constant + palette_size_const: u8, // == CONSTANT + data_constant: u16, + }, + struct { // indirect inline + palette_size_indirect_inline: u8, // <= INLINE_MAX, != DIRECT, != CONSTANT + palette_inline: [INLINE_MAX]u16, + data_indirect: *[*]u8, + }, + struct { // indirect ptr + palette_size_indirect_ptr: u8, // > INLINE_MAX + palette_ptr: *[*]u16, + // data_indirect: *[*]u8, + // (though it would result in an incorrect offset... yeah, + // i don't know what i was thinking here at all.) + }, +}; + +export fn new(palette_size: u8, arraylen: size) Array = { + let array = Array { + palette_size = palette_size, + }; + + if (palette_size == DIRECT) { + array.data_direct = + alloc([]: [0]u16, arraylen): *[*]u16; + } else if (palette_size != CONSTANT) { + array.data_indirect = alloc([]: [0]u8, + indirect_size(palette_size, arraylen)): *[*]u8; + if (palette_size > INLINE_MAX) { + array.palette_ptr = + alloc([]: [0]u16, palette_size): *[*]u16; + }; + }; + + return array; +}; + +export fn clear(array: *Array, fill_value: u16) void = { + if (array.palette_size == DIRECT) { + free(array.data_direct); + } else if (array.palette_size != CONSTANT) { + free(array.data_indirect); + if (array.palette_size > INLINE_MAX) + free(array.palette_ptr); + }; + + array.palette_size = CONSTANT; + array.data_constant = fill_value; +}; + +// XXX: should be @inline +export fn get(array: *Array, i: size) u16 = { + if (array.palette_size == DIRECT) { + return array.data_direct[i]; + } else if (array.palette_size == CONSTANT) { + return 0; + } else { + const log2nbits = palette_log2nbits(array.palette_size); + const nbits = 1 << log2nbits; + const valuemask = (1 << nbits) - 1; + const log2nperbyte = 3 - log2nbits; + const nperbyte = 1 << log2nperbyte; + const indexlow = nperbyte - 1; + + const byte = array.data_indirect[i >> log2nperbyte]; + const shift = (i: u8 & indexlow) << log2nbits; + return (byte >> shift) & valuemask; + }; +}; + +// XXX: should be @inline +export fn set(array: *Array, i: size, ref: u16) void = { + if (array.palette_size == DIRECT) { + array.data_direct[i] = ref; + } else if (array.palette_size == CONSTANT) { + assert(ref == 0); + } else { + const log2nbits = palette_log2nbits(array.palette_size); + const nbits = 1 << log2nbits; + const valuemask = (1 << nbits) - 1; + const log2nperbyte = 3 - log2nbits; + const nperbyte = 1 << log2nperbyte; + const indexlow = nperbyte - 1; + + const byte = &array.data_indirect[i >> log2nperbyte]; + const shift = (i: u8 & indexlow) << log2nbits; + *byte = *byte & ~(valuemask << shift) | ref: u8 << shift; + }; +}; + +// XXX: should be @inline +export fn get_palette(array: *Array) []u16 = { + if (array.palette_size == DIRECT) { + abort(); + } else if (array.palette_size == CONSTANT) { + return &array.data_constant: *[1]u16; + } else if (array.palette_size <= INLINE_MAX) { + return array.palette_inline[..array.palette_size]; + } else { + return array.palette_ptr[..array.palette_size]; + }; +}; + +// XXX: should be @inline +export fn lookup(array: *Array, ref: u16) u16 = { + if (array.palette_size == DIRECT) { + return ref; + }; + return get_palette(array)[ref]; +}; + +// XXX: should be @inline +export fn indirect_size(palette_size: u8, arraylen: size) size = + arraylen << palette_log2nbits(palette_size) >> 3; + +// XXX: should be @inline +export fn palette_log2nbits(palette_size: u8) u8 = { + assert(palette_size != DIRECT); + const nbits = math::bit_size_u8(palette_size - 1); + return math::bit_size_u8(nbits - 1); +}; + +export fn grow_palette(array: *Array, arraylen: size, newsize: u8) void = { + if (array.palette_size == newsize) return; + assert( + (array.palette_size - 1) < (newsize - 1), + "new size must be >= old size" + ); + + let newarray = *array; + newarray.palette_size = newsize; + + defer *array = newarray; + + // By this point we know that the palette has grown in size, so it + // always needs to be reallocated unless the new size is DIRECT, + // in which case there will be no palette. + + const palette = get_palette(array); + + if (newsize == DIRECT) { + void; + } else if (newsize <= INLINE_MAX) { + newarray.palette_inline[..len(palette)] = palette; + } else { + let newpalette = alloc(palette, newsize); + newarray.palette_ptr = newpalette: *[*]u16; + }; + + defer if (array.palette_size > INLINE_MAX) { + free(array.palette_ptr); + }; + + if (array.palette_size == CONSTANT) { + if (newsize == DIRECT) { + newarray.data_direct = alloc([array.data_constant...], + arraylen): *[*]u16; + } else { + newarray.data_indirect = alloc([0...], + indirect_size(newsize, arraylen)): *[*]u8; + }; + + return; + }; + + if (newsize == DIRECT) { + newarray.data_direct = alloc([]: [0]u16, arraylen): *[*]u16; + + for (let i = 0z; i < arraylen; i += 1) { + newarray.data_direct[i] = palette[get(array, i)]; + }; + + free(array.data_indirect); + return; + }; + + // We need to reallocate the data array if the number of bits per item + // increased. + + const log2nbits = palette_log2nbits(array.palette_size); + const log2newnbits = palette_log2nbits(newsize); + + if (log2nbits != log2newnbits) { + newarray.data_indirect = alloc([]: [0]u8, + indirect_size(newsize, arraylen)): *[*]u8; + + for (let i = 0z; i < arraylen; i += 1) { + set(&newarray, i, get(array, i)); + }; + + free(array.data_indirect); + }; +}; -- cgit v1.2.3