radiance · Radiance self-hosting compiler

test/tests/prog.lzw.rad 6.7 KiB raw

//! returns: 0
//! LZW compression and decompression.
//! Implement the Lempel-Ziv-Welch algorithm with a fixed-size dictionary.
//! Encode a byte buffer, decode it, and verify perfect round-trip.

const MAX_DICT: u32 = 512;
const INIT_DICT: u32 = 258;
const CLEAR_CODE: u32 = 256;
const EOI_CODE: u32 = 257;

record DictEntry {
    prefix: u32,
    suffix: u8,
}

record LzwState {
    encDict: *mut [DictEntry],
    encDictSize: u32,
    decDict: *mut [DictEntry],
    decDictSize: u32,
    encoded: *mut [u32],
    encLen: u32,
    decoded: *mut [u8],
    decLen: u32,
    temp: *mut [u8],
}

fn initEncDict(s: *mut LzwState) {
    s.encDictSize = INIT_DICT;
    let mut i: u32 = 0;
    while i < 256 {
        s.encDict[i] = DictEntry { prefix: 0xFFFF, suffix: i as u8 };
        i += 1;
    }
}

fn initDecDict(s: *mut LzwState) {
    s.decDictSize = INIT_DICT;
    let mut i: u32 = 0;
    while i < 256 {
        s.decDict[i] = DictEntry { prefix: 0xFFFF, suffix: i as u8 };
        i += 1;
    }
}

fn dictLookup(s: *LzwState, prefix: u32, suffix: u8) -> u32 {
    let mut i: u32 = 0;
    while i < s.encDictSize {
        if s.encDict[i].prefix == prefix and s.encDict[i].suffix == suffix {
            return i;
        }
        i += 1;
    }
    return 0xFFFFFFFF;
}

fn dictAdd(s: *mut LzwState, prefix: u32, suffix: u8) {
    if s.encDictSize < MAX_DICT {
        s.encDict[s.encDictSize] = DictEntry { prefix, suffix };
        s.encDictSize += 1;
    }
}

fn emitCode(s: *mut LzwState, code: u32) {
    s.encoded[s.encLen] = code;
    s.encLen += 1;
}

fn encode(s: *mut LzwState, data: *[u8]) {
    initEncDict(s);
    s.encLen = 0;

    if data.len == 0 {
        emitCode(s, EOI_CODE);
        return;
    }

    let mut w: u32 = data[0] as u32;
    let mut i: u32 = 1;

    while i < data.len {
        let c: u8 = data[i];
        let wc: u32 = dictLookup(s, w, c);
        if wc != 0xFFFFFFFF {
            w = wc;
        } else {
            emitCode(s, w);
            dictAdd(s, w, c);
            w = c as u32;
        }
        i += 1;
    }
    emitCode(s, w);
    emitCode(s, EOI_CODE);
}

fn decodeString(s: *mut LzwState, code: u32) -> u32 {
    let mut len: u32 = 0;
    let mut c: u32 = code;
    while c != 0xFFFF and c < s.decDictSize {
        s.temp[len] = s.decDict[c].suffix;
        len += 1;
        c = s.decDict[c].prefix;
    }
    let mut a: u32 = 0;
    let mut b: u32 = len - 1;
    while a < b {
        let tmp: u8 = s.temp[a];
        s.temp[a] = s.temp[b];
        s.temp[b] = tmp;
        a += 1;
        b -= 1;
    }
    return len;
}

fn firstByte(s: *LzwState, code: u32) -> u8 {
    let mut c: u32 = code;
    while s.decDict[c].prefix != 0xFFFF and s.decDict[c].prefix < s.decDictSize {
        c = s.decDict[c].prefix;
    }
    return s.decDict[c].suffix;
}

fn decDictAdd(s: *mut LzwState, prefix: u32, suffix: u8) {
    if s.decDictSize < MAX_DICT {
        s.decDict[s.decDictSize] = DictEntry { prefix, suffix };
        s.decDictSize += 1;
    }
}

fn outputByte(s: *mut LzwState, b: u8) {
    s.decoded[s.decLen] = b;
    s.decLen += 1;
}

fn decode(s: *mut LzwState) {
    initDecDict(s);
    s.decLen = 0;

    if s.encLen == 0 {
        return;
    }

    let mut pos: u32 = 0;
    let mut code: u32 = s.encoded[pos];
    pos += 1;

    if code == EOI_CODE {
        return;
    }

    outputByte(s, code as u8);
    let mut prevCode: u32 = code;

    while pos < s.encLen {
        code = s.encoded[pos];
        pos += 1;

        if code == EOI_CODE {
            return;
        }

        if code < s.decDictSize {
            let len: u32 = decodeString(s, code);
            let mut i: u32 = 0;
            while i < len {
                outputByte(s, s.temp[i]);
                i += 1;
            }
            decDictAdd(s, prevCode, s.temp[0]);
        } else {
            let fb: u8 = firstByte(s, prevCode);
            let len: u32 = decodeString(s, prevCode);
            let mut i: u32 = 0;
            while i < len {
                outputByte(s, s.temp[i]);
                i += 1;
            }
            outputByte(s, fb);
            decDictAdd(s, prevCode, fb);
        }
        prevCode = code;
    }
}

fn testSimple(s: *mut LzwState) -> i32 {
    let data: *[u8] = "ABABABABAB";
    encode(s, data);

    assert s.encoded[s.encLen - 1] == EOI_CODE;

    decode(s);
    assert s.decLen == 10;
    let mut i: u32 = 0;
    while i < 10 {
        assert s.decoded[i] == data[i];
        i += 1;
    }
    return 0;
}

fn testDistinct(s: *mut LzwState) -> i32 {
    let data: [u8; 16] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
    encode(s, &data[..]);

    decode(s);
    assert s.decLen == 16;
    let mut i: u32 = 0;
    while i < 16 {
        assert s.decoded[i] == data[i];
        i += 1;
    }
    return 0;
}

fn testRepetitive(s: *mut LzwState) -> i32 {
    let mut data: [u8; 64] = [65; 64];
    encode(s, &data[..]);

    assert s.encLen < 32;

    decode(s);
    assert s.decLen == 64;
    let mut i: u32 = 0;
    while i < 64 {
        assert s.decoded[i] == 65;
        i += 1;
    }
    return 0;
}

fn testMixed(s: *mut LzwState) -> i32 {
    let data: *[u8] = "TOBEORNOTTOBEORTOBEORNOT";
    encode(s, data);

    decode(s);
    assert s.decLen == 24;
    let mut i: u32 = 0;
    while i < 24 {
        assert s.decoded[i] == data[i];
        i += 1;
    }

    assert s.encLen - 1 < 24;

    return 0;
}

fn testEmpty(s: *mut LzwState) -> i32 {
    encode(s, &[]);
    assert s.encLen == 1;
    assert s.encoded[0] == EOI_CODE;

    decode(s);
    assert s.decLen == 0;
    return 0;
}

fn testSingle(s: *mut LzwState) -> i32 {
    let data: *[u8] = "*";
    encode(s, data);

    decode(s);
    assert s.decLen == 1;
    assert s.decoded[0] == 42;
    return 0;
}

@default fn main() -> i32 {
    let mut encDict: [DictEntry; 512] = [DictEntry { prefix: 0xFFFF, suffix: 0 }; 512];
    let mut decDict: [DictEntry; 512] = [DictEntry { prefix: 0xFFFF, suffix: 0 }; 512];
    let mut encoded: [u32; 512] = [0; 512];
    let mut decoded: [u8; 256] = [0; 256];
    let mut temp: [u8; 256] = [0; 256];

    let mut s: LzwState = LzwState {
        encDict: &mut encDict[..],
        encDictSize: 0,
        decDict: &mut decDict[..],
        decDictSize: 0,
        encoded: &mut encoded[..],
        encLen: 0,
        decoded: &mut decoded[..],
        decLen: 0,
        temp: &mut temp[..],
    };

    let r1: i32 = testSimple(&mut s);
    if r1 != 0 { return 10 + r1; }

    let r2: i32 = testDistinct(&mut s);
    if r2 != 0 { return 20 + r2; }

    let r3: i32 = testRepetitive(&mut s);
    if r3 != 0 { return 30 + r3; }

    let r4: i32 = testMixed(&mut s);
    if r4 != 0 { return 40 + r4; }

    let r5: i32 = testEmpty(&mut s);
    if r5 != 0 { return 50 + r5; }

    let r6: i32 = testSingle(&mut s);
    if r6 != 0 { return 60 + r6; }

    return 0;
}

1	//! returns: 0
2	//! LZW compression and decompression.
3	//! Implement the Lempel-Ziv-Welch algorithm with a fixed-size dictionary.
4	//! Encode a byte buffer, decode it, and verify perfect round-trip.
5
6	const MAX_DICT: u32 = 512;
7	const INIT_DICT: u32 = 258;
8	const CLEAR_CODE: u32 = 256;
9	const EOI_CODE: u32 = 257;
10
11	record DictEntry {
12	prefix: u32,
13	suffix: u8,
14	}
15
16	record LzwState {
17	encDict: *mut [DictEntry],
18	encDictSize: u32,
19	decDict: *mut [DictEntry],
20	decDictSize: u32,
21	encoded: *mut [u32],
22	encLen: u32,
23	decoded: *mut [u8],
24	decLen: u32,
25	temp: *mut [u8],
26	}
27
28	fn initEncDict(s: *mut LzwState) {
29	s.encDictSize = INIT_DICT;
30	let mut i: u32 = 0;
31	while i < 256 {
32	s.encDict[i] = DictEntry { prefix: 0xFFFF, suffix: i as u8 };
33	i += 1;
34	}
35	}
36
37	fn initDecDict(s: *mut LzwState) {
38	s.decDictSize = INIT_DICT;
39	let mut i: u32 = 0;
40	while i < 256 {
41	s.decDict[i] = DictEntry { prefix: 0xFFFF, suffix: i as u8 };
42	i += 1;
43	}
44	}
45
46	fn dictLookup(s: *LzwState, prefix: u32, suffix: u8) -> u32 {
47	let mut i: u32 = 0;
48	while i < s.encDictSize {
49	if s.encDict[i].prefix == prefix and s.encDict[i].suffix == suffix {
50	return i;
51	}
52	i += 1;
53	}
54	return 0xFFFFFFFF;
55	}
56
57	fn dictAdd(s: *mut LzwState, prefix: u32, suffix: u8) {
58	if s.encDictSize < MAX_DICT {
59	s.encDict[s.encDictSize] = DictEntry { prefix, suffix };
60	s.encDictSize += 1;
61	}
62	}
63
64	fn emitCode(s: *mut LzwState, code: u32) {
65	s.encoded[s.encLen] = code;
66	s.encLen += 1;
67	}
68
69	fn encode(s: mut LzwState, data: [u8]) {
70	initEncDict(s);
71	s.encLen = 0;
72
73	if data.len == 0 {
74	emitCode(s, EOI_CODE);
75	return;
76	}
77
78	let mut w: u32 = data[0] as u32;
79	let mut i: u32 = 1;
80
81	while i < data.len {
82	let c: u8 = data[i];
83	let wc: u32 = dictLookup(s, w, c);
84	if wc != 0xFFFFFFFF {
85	w = wc;
86	} else {
87	emitCode(s, w);
88	dictAdd(s, w, c);
89	w = c as u32;
90	}
91	i += 1;
92	}
93	emitCode(s, w);
94	emitCode(s, EOI_CODE);
95	}
96
97	fn decodeString(s: *mut LzwState, code: u32) -> u32 {
98	let mut len: u32 = 0;
99	let mut c: u32 = code;
100	while c != 0xFFFF and c < s.decDictSize {
101	s.temp[len] = s.decDict[c].suffix;
102	len += 1;
103	c = s.decDict[c].prefix;
104	}
105	let mut a: u32 = 0;
106	let mut b: u32 = len - 1;
107	while a < b {
108	let tmp: u8 = s.temp[a];
109	s.temp[a] = s.temp[b];
110	s.temp[b] = tmp;
111	a += 1;
112	b -= 1;
113	}
114	return len;
115	}
116
117	fn firstByte(s: *LzwState, code: u32) -> u8 {
118	let mut c: u32 = code;
119	while s.decDict[c].prefix != 0xFFFF and s.decDict[c].prefix < s.decDictSize {
120	c = s.decDict[c].prefix;
121	}
122	return s.decDict[c].suffix;
123	}
124
125	fn decDictAdd(s: *mut LzwState, prefix: u32, suffix: u8) {
126	if s.decDictSize < MAX_DICT {
127	s.decDict[s.decDictSize] = DictEntry { prefix, suffix };
128	s.decDictSize += 1;
129	}
130	}
131
132	fn outputByte(s: *mut LzwState, b: u8) {
133	s.decoded[s.decLen] = b;
134	s.decLen += 1;
135	}
136
137	fn decode(s: *mut LzwState) {
138	initDecDict(s);
139	s.decLen = 0;
140
141	if s.encLen == 0 {
142	return;
143	}
144
145	let mut pos: u32 = 0;
146	let mut code: u32 = s.encoded[pos];
147	pos += 1;
148
149	if code == EOI_CODE {
150	return;
151	}
152
153	outputByte(s, code as u8);
154	let mut prevCode: u32 = code;
155
156	while pos < s.encLen {
157	code = s.encoded[pos];
158	pos += 1;
159
160	if code == EOI_CODE {
161	return;
162	}
163
164	if code < s.decDictSize {
165	let len: u32 = decodeString(s, code);
166	let mut i: u32 = 0;
167	while i < len {
168	outputByte(s, s.temp[i]);
169	i += 1;
170	}
171	decDictAdd(s, prevCode, s.temp[0]);
172	} else {
173	let fb: u8 = firstByte(s, prevCode);
174	let len: u32 = decodeString(s, prevCode);
175	let mut i: u32 = 0;
176	while i < len {
177	outputByte(s, s.temp[i]);
178	i += 1;
179	}
180	outputByte(s, fb);
181	decDictAdd(s, prevCode, fb);
182	}
183	prevCode = code;
184	}
185	}
186
187	fn testSimple(s: *mut LzwState) -> i32 {
188	let data: *[u8] = "ABABABABAB";
189	encode(s, data);
190
191	assert s.encoded[s.encLen - 1] == EOI_CODE;
192
193	decode(s);
194	assert s.decLen == 10;
195	let mut i: u32 = 0;
196	while i < 10 {
197	assert s.decoded[i] == data[i];
198	i += 1;
199	}
200	return 0;
201	}
202
203	fn testDistinct(s: *mut LzwState) -> i32 {
204	let data: [u8; 16] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
205	encode(s, &data[..]);
206
207	decode(s);
208	assert s.decLen == 16;
209	let mut i: u32 = 0;
210	while i < 16 {
211	assert s.decoded[i] == data[i];
212	i += 1;
213	}
214	return 0;
215	}
216
217	fn testRepetitive(s: *mut LzwState) -> i32 {
218	let mut data: [u8; 64] = [65; 64];
219	encode(s, &data[..]);
220
221	assert s.encLen < 32;
222
223	decode(s);
224	assert s.decLen == 64;
225	let mut i: u32 = 0;
226	while i < 64 {
227	assert s.decoded[i] == 65;
228	i += 1;
229	}
230	return 0;
231	}
232
233	fn testMixed(s: *mut LzwState) -> i32 {
234	let data: *[u8] = "TOBEORNOTTOBEORTOBEORNOT";
235	encode(s, data);
236
237	decode(s);
238	assert s.decLen == 24;
239	let mut i: u32 = 0;
240	while i < 24 {
241	assert s.decoded[i] == data[i];
242	i += 1;
243	}
244
245	assert s.encLen - 1 < 24;
246
247	return 0;
248	}
249
250	fn testEmpty(s: *mut LzwState) -> i32 {
251	encode(s, &[]);
252	assert s.encLen == 1;
253	assert s.encoded[0] == EOI_CODE;
254
255	decode(s);
256	assert s.decLen == 0;
257	return 0;
258	}
259
260	fn testSingle(s: *mut LzwState) -> i32 {
261	let data: [u8] = "";
262	encode(s, data);
263
264	decode(s);
265	assert s.decLen == 1;
266	assert s.decoded[0] == 42;
267	return 0;
268	}
269
270	@default fn main() -> i32 {
271	let mut encDict: [DictEntry; 512] = [DictEntry { prefix: 0xFFFF, suffix: 0 }; 512];
272	let mut decDict: [DictEntry; 512] = [DictEntry { prefix: 0xFFFF, suffix: 0 }; 512];
273	let mut encoded: [u32; 512] = [0; 512];
274	let mut decoded: [u8; 256] = [0; 256];
275	let mut temp: [u8; 256] = [0; 256];
276
277	let mut s: LzwState = LzwState {
278	encDict: &mut encDict[..],
279	encDictSize: 0,
280	decDict: &mut decDict[..],
281	decDictSize: 0,
282	encoded: &mut encoded[..],
283	encLen: 0,
284	decoded: &mut decoded[..],
285	decLen: 0,
286	temp: &mut temp[..],
287	};
288
289	let r1: i32 = testSimple(&mut s);
290	if r1 != 0 { return 10 + r1; }
291
292	let r2: i32 = testDistinct(&mut s);
293	if r2 != 0 { return 20 + r2; }
294
295	let r3: i32 = testRepetitive(&mut s);
296	if r3 != 0 { return 30 + r3; }
297
298	let r4: i32 = testMixed(&mut s);
299	if r4 != 0 { return 40 + r4; }
300
301	let r5: i32 = testEmpty(&mut s);
302	if r5 != 0 { return 50 + r5; }
303
304	let r6: i32 = testSingle(&mut s);
305	if r6 != 0 { return 60 + r6; }
306
307	return 0;
308	}