| // Copyright 2017 The Puffs Authors. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| // TODO: some mechanism for fixing the error code's value, such as a trailing |
| // "= 100", to maintain API stability. |
| pub error "LZW code is out of range" |
| pub error "LZW prefix chain is cyclical" |
| |
| pub struct lzw_decoder?( |
| literal_width u32[2..8] = 8, |
| stack[4096] u8, |
| suffixes[4096] u8, |
| prefixes[4096] u16[..4095], |
| ) |
| |
| // TODO: add a ! as this function is impure. |
| pub func lzw_decoder.set_literal_width(lw u32[2..8] = 8)() { |
| this.literal_width = in.lw |
| } |
| |
| pub func lzw_decoder.decode?(dst writer1, src reader1)() { |
| // These variables don't change over the lifetime of this func. |
| var clear_code u32[4..256] = (1 as u32) << this.literal_width |
| var end_code u32[5..257] = clear_code + 1 |
| |
| // These variables do change. |
| // |
| // save_code is the code for which, after decoding a code, we save what the |
| // next back-reference expands to. The README.md file also calls this value |
| // `max`. 4096 means do not save. |
| var save_code u32[..4096] = end_code |
| var prev_code u32[..4095] |
| var width u32[..12] = this.literal_width + 1 |
| |
| // These variables yield src's bits in Least Significant Bits order. |
| var bits u32 |
| var n_bits u32 |
| |
| while true, |
| pre n_bits < 8, |
| { |
| assert n_bits < (width + 8) via "a < (b + c): a < c; 0 <= b"() |
| while n_bits < width, |
| inv n_bits < (width + 8), |
| post n_bits >= width, |
| { |
| assert n_bits < 12 via "a < b: a < c; c <= b"(c:width) |
| bits |= (in.src.read_u8?() as u32) << n_bits |
| n_bits += 8 |
| } |
| var code u32[..4095] = bits.low_bits(n:width) |
| bits >>= width |
| n_bits -= width |
| |
| if code < clear_code { |
| assert code < 256 via "a < b: a < c; c <= b"(c:clear_code) |
| in.dst.write_u8?(x:code as u8) |
| if save_code <= 4095 { |
| this.suffixes[save_code] = code as u8 |
| this.prefixes[save_code] = prev_code as u16 |
| } |
| |
| } else if code == clear_code { |
| save_code = end_code |
| prev_code = 0 |
| width = this.literal_width + 1 |
| continue |
| |
| } else if code == end_code { |
| return |
| |
| } else if code <= save_code { |
| var s u32[..4095] = 4095 |
| var c u32[..4095] = code |
| |
| if code == save_code { |
| s -= 1 |
| c = prev_code |
| } |
| |
| while c >= clear_code, |
| inv n_bits < 8, |
| post c < 256 via "a < b: a < c; c <= b"(c:clear_code), |
| { |
| this.stack[s] = this.suffixes[c] |
| if s == 0 { |
| return error "LZW prefix chain is cyclical" |
| } |
| s -= 1 |
| c = this.prefixes[c] as u32 |
| } |
| this.stack[s] = c as u8 |
| |
| if code == save_code { |
| this.stack[4095] = c as u8 |
| } |
| |
| while true, |
| inv n_bits < 8, |
| inv c < 256, |
| { |
| var expansion[] u8 = this.stack[s:] |
| // TODO: "x:" instead of "s:" should be a compiler error. |
| var n_copied u64 = in.dst.copy_from_slice(x:expansion) |
| if n_copied == expansion.length() { |
| break |
| } |
| s = (s + ((n_copied & 4095) as u32)) & 4095 |
| // TODO: "closed for writes" instead? |
| return suspension "short write" |
| } |
| |
| if save_code <= 4095 { |
| this.suffixes[save_code] = c as u8 |
| this.prefixes[save_code] = prev_code as u16 |
| } |
| |
| } else { |
| return error "LZW code is out of range" |
| } |
| |
| if save_code <= 4095 { |
| save_code += 1 |
| if (save_code == ((1 as u32) << width)) and (width < 12) { |
| width += 1 |
| } |
| } |
| prev_code = code |
| } |
| } |