Compress Large Data Structures by Packing Bit Fields

Topic Overview

Shrink Structures With Bit Fields

Networking headers, bloom-filter bitmaps, and game entity flags pack dozens of booleans into a few bytes. Bit packing cuts memory bandwidth and improves cache occupancy when you touch thousands of records per frame.

Manual vs Compiler Bit Fields

C bit-fields are convenient but implementation-defined. Manual shifts mask and store flags in uint32_t words for portable layouts.

cCopy
Loading…

• Document bit layout in comments for the next maintainer
• Unaligned packed fields may cost extra shifts on read/modify/write
• SIMD prefers separate arrays over packed scalars when updating one field
• Measure memory bytes and cache misses together

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will pack multiple small integers into one word and unpack them correctly. This exercise asks you to demonstrate memory savings on a large array of packed records.

Your Task

A game entity with an alive flag, 10 bits of HP, two 12-bit coordinates and a few small enums fits in 43 bits. A normal C struct spends 10 bytes on it, because each field takes a whole char, short or int. Pack the fields into one 64-bit word with shifts and masks (the portable alternative to C bit-fields, whose layout is implementation-defined), including signed fields that need sign extension on the way out, and measure the saving.

Input

cCopy
Loading…

Rules

• Layout. Fields are packed LSB-first: the first field occupies bits 0.., and each next field starts where the previous one ended. A field that would exceed 64 bits in total is rejected: field NAME: does not fit (U of 64 bits used).
• Unpacked struct. Each field uses the smallest C type that holds it (1-8 bits: 1 byte, up to 16: 2, up to 32: 4, up to 64: 8), in declaration order with natural alignment. The total is rounded up to the largest alignment.
• Packed size = ceil(total bits / 8) bytes. records N compares N packed and N unpacked records, and the saving is rounded half up to 1 decimal.
• pack checks ranges: unsigned fields hold 0..2^b−1, and signed fields −2^(b−1)..2^(b−1)−1. Values are parsed as signed 64-bit integers, so unsigned fields of 63 or 64 bits accept at most 2^63−1. Otherwise print pack: NAME=V does not fit in b signed|unsigned bits and nothing else. It prints the word as 0x followed by 2 × packed-bytes hex digits.
• unpack sign-extends signed fields. If bits above the last field are set, it first prints unpack: warning, bits above bit T are set and ignored (T = total − 1).
• Errors: field NAME: 1..64 bits, pack: unknown field NAME, and pack: expected NAME=VALUE, got TEXT.

Output

cCopy
Loading…

Layout lines use " %-10s bits %2d..%-2d (%d bit(s), signed|unsigned)".

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Insert with w = (w & ~(mask << shift)) | ((v & mask) << shift), and extract with (w >> shift) & mask, working in uint64_t throughout.
2. Sign-extend signed fields yourself: if the top bit of the field is set, OR in the high bits.

Hidden tests cover a pack/unpack round trip, a single 64-bit field, 1-bit signed fields (range −1..0), stray high bits on unpack, fields that no longer fit, and malformed pack arguments.