decode_lzw.wuffs 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362
  1. // Copyright 2017 The Wuffs Authors.
  2. //
  3. // Licensed under the Apache License, Version 2.0 (the "License");
  4. // you may not use this file except in compliance with the License.
  5. // You may obtain a copy of the License at
  6. //
  7. // https://www.apache.org/licenses/LICENSE-2.0
  8. //
  9. // Unless required by applicable law or agreed to in writing, software
  10. // distributed under the License is distributed on an "AS IS" BASIS,
  11. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. // See the License for the specific language governing permissions and
  13. // limitations under the License.
  14. pub status "#bad code"
  15. pri status "#internal error: inconsistent I/O"
  16. // TODO: move bulk data buffers like decoder.suffixes or decoder.output into
  17. // the workbuf? The first attempt at this was a performance regression for
  18. // decoding all but the smallest GIFs. See these git commits for numbers:
  19. // - 49627b4 Flatten the lzw.decoder.suffixes array
  20. // - f877fb2 Use the workbuf instead of lzw.decoder.suffixes
  21. // - 85be5b9 Delete the obsolete lzw.decoder.suffixes array
  22. // and the roll back has combined numbers:
  23. // - 3056a84 Roll back 3 recent lzw.decoder.suffixes commits
  24. pub const decoder_workbuf_len_max_incl_worst_case base.u64 = 0
  25. pub struct decoder?(
  26. // set_literal_width_arg is 1 plus the saved argument passed to
  27. // set_literal_width. This is assigned to the literal_width field at the
  28. // start of decode_io_writer. During that method, calling set_literal_width
  29. // will change set_literal_width_arg but not literal_width.
  30. set_literal_width_arg base.u32[..9],
  31. // read_from state that does not change during a decode call.
  32. literal_width base.u32[..8],
  33. clear_code base.u32[..256],
  34. end_code base.u32[..257],
  35. // read_from state that does change during a decode call.
  36. save_code base.u32[..4096],
  37. prev_code base.u32[..4095],
  38. width base.u32[..12],
  39. bits base.u32,
  40. n_bits base.u32[..31],
  41. output_ri base.u32[..8191],
  42. output_wi base.u32[..8191],
  43. // read_from return value. The read_from method effectively returns a
  44. // base.u32 to show how decode should continue after calling write_to. That
  45. // value needs to be saved across write_to's possible suspension, so we
  46. // might as well save it explicitly as a decoder field.
  47. read_from_return_value base.u32,
  48. // read_from per-code state.
  49. prefixes array[4096] base.u16[..4095],
  50. util base.utility,
  51. )(
  52. // read_from per-code state.
  53. suffixes array[4096] array[8] base.u8,
  54. // lm1s is the "length minus 1"s of the values for the implicit key-value
  55. // table in this decoder. See std/lzw/README.md for more detail.
  56. lm1s array[4096] base.u16,
  57. // output[output_ri:output_wi] is the buffered output, connecting read_from
  58. // with write_to and flush.
  59. output array[8192 + 7] base.u8,
  60. )
  61. pub func decoder.set_literal_width!(lw base.u32[..8]) {
  62. this.set_literal_width_arg = args.lw + 1
  63. }
  64. pub func decoder.workbuf_len() base.range_ii_u64 {
  65. return this.util.make_range_ii_u64(min_incl:0, max_incl:0)
  66. }
  67. pub func decoder.decode_io_writer?(dst base.io_writer, src base.io_reader, workbuf slice base.u8) {
  68. var i base.u32[..8191]
  69. // Initialize read_from state.
  70. this.literal_width = 8
  71. if this.set_literal_width_arg > 0 {
  72. this.literal_width = this.set_literal_width_arg - 1
  73. }
  74. this.clear_code = (1 as base.u32) << this.literal_width
  75. this.end_code = this.clear_code + 1
  76. this.save_code = this.end_code
  77. this.prev_code = this.end_code
  78. this.width = this.literal_width + 1
  79. this.bits = 0
  80. this.n_bits = 0
  81. this.output_ri = 0
  82. this.output_wi = 0
  83. i = 0
  84. while i < this.clear_code {
  85. assert i < 256 via "a < b: a < c; c <= b"(c:this.clear_code)
  86. this.lm1s[i] = 0
  87. this.suffixes[i][0] = i as base.u8
  88. i += 1
  89. }
  90. while true {
  91. this.read_from!(src:args.src)
  92. if this.output_wi > 0 {
  93. this.write_to?(dst:args.dst)
  94. }
  95. if this.read_from_return_value == 0 {
  96. break
  97. } else if this.read_from_return_value == 1 {
  98. continue
  99. } else if this.read_from_return_value == 2 {
  100. yield? base."$short read"
  101. } else if this.read_from_return_value == 3 {
  102. return "#bad code"
  103. } else {
  104. return "#internal error: inconsistent I/O"
  105. }
  106. }
  107. }
  108. pri func decoder.read_from!(src base.io_reader) {
  109. var clear_code base.u32[..256]
  110. var end_code base.u32[..257]
  111. var save_code base.u32[..4096]
  112. var prev_code base.u32[..4095]
  113. var width base.u32[..12]
  114. var bits base.u32
  115. var n_bits base.u32[..31]
  116. var output_wi base.u32[..8191]
  117. var code base.u32[..4095]
  118. var c base.u32[..4095]
  119. var o base.u32[..8191]
  120. var steps base.u32
  121. var first_byte base.u8
  122. var lm1_b base.u16[..4095]
  123. var lm1_a base.u16[..4095]
  124. clear_code = this.clear_code
  125. end_code = this.end_code
  126. save_code = this.save_code
  127. prev_code = this.prev_code
  128. width = this.width
  129. bits = this.bits
  130. n_bits = this.n_bits
  131. output_wi = this.output_wi
  132. while true {
  133. if n_bits < width {
  134. assert n_bits < 12 via "a < b: a < c; c <= b"(c:width)
  135. if args.src.available() >= 4 {
  136. // Read 4 bytes, using the "Variant 4" technique of
  137. // https://fgiesen.wordpress.com/2018/02/20/reading-bits-in-far-too-many-ways-part-2/
  138. bits |= args.src.peek_u32le() ~mod<< n_bits
  139. args.src.skip_fast!(actual:(31 - n_bits) >> 3, worst_case:3)
  140. n_bits |= 24
  141. assert width <= n_bits via "a <= b: a <= c; c <= b"(c:12)
  142. assert n_bits >= width via "a >= b: b <= a"()
  143. } else if args.src.available() <= 0 {
  144. this.read_from_return_value = 2
  145. break
  146. } else {
  147. bits |= args.src.peek_u8_as_u32() << n_bits
  148. args.src.skip_fast!(actual:1, worst_case:1)
  149. n_bits += 8
  150. if n_bits >= width {
  151. // No-op.
  152. } else if args.src.available() <= 0 {
  153. this.read_from_return_value = 2
  154. break
  155. } else {
  156. bits |= args.src.peek_u8_as_u32() << n_bits
  157. args.src.skip_fast!(actual:1, worst_case:1)
  158. n_bits += 8
  159. assert width <= n_bits via "a <= b: a <= c; c <= b"(c:12)
  160. assert n_bits >= width via "a >= b: b <= a"()
  161. // This if condition is always false, but for some unknown
  162. // reason, removing it worsens the benchmarks slightly.
  163. if n_bits < width {
  164. this.read_from_return_value = 4
  165. break
  166. }
  167. }
  168. }
  169. }
  170. code = bits.low_bits(n:width)
  171. bits >>= width
  172. n_bits -= width
  173. if code < clear_code {
  174. assert code < 256 via "a < b: a < c; c <= b"(c:clear_code)
  175. this.output[output_wi] = code as base.u8
  176. output_wi = (output_wi + 1) & 8191
  177. if save_code <= 4095 {
  178. lm1_a = (this.lm1s[prev_code] ~mod+ 1) & 4095
  179. this.lm1s[save_code] = lm1_a
  180. if (lm1_a % 8) <> 0 {
  181. this.prefixes[save_code] = this.prefixes[prev_code]
  182. this.suffixes[save_code] = this.suffixes[prev_code]
  183. this.suffixes[save_code][lm1_a % 8] = code as base.u8
  184. } else {
  185. this.prefixes[save_code] = prev_code as base.u16
  186. this.suffixes[save_code][0] = code as base.u8
  187. }
  188. save_code += 1
  189. if width < 12 {
  190. width += 1 & (save_code >> width)
  191. }
  192. prev_code = code
  193. }
  194. } else if code <= end_code {
  195. if code == end_code {
  196. this.read_from_return_value = 0
  197. break
  198. }
  199. save_code = end_code
  200. prev_code = end_code
  201. width = this.literal_width + 1
  202. } else if code <= save_code {
  203. c = code
  204. if code == save_code {
  205. c = prev_code
  206. }
  207. // Letting old_wi and new_wi denote the values of output_wi before
  208. // and after these two lines of code, the decoded bytes will be
  209. // written to output[old_wi:new_wi]. They will be written
  210. // back-to-front, 8 bytes at a time, starting by writing
  211. // output[o:o + 8], which will contain output[new_wi - 1].
  212. //
  213. // In the special case that code == save_code, the decoded bytes
  214. // contain an extra copy (at the end) of the first byte, and will
  215. // be written to output[old_wi:new_wi + 1].
  216. o = (output_wi + ((this.lm1s[c] as base.u32) & 0xFFFFFFF8)) & 8191
  217. output_wi = (output_wi + 1 + (this.lm1s[c] as base.u32)) & 8191
  218. steps = (this.lm1s[c] as base.u32) >> 3
  219. while true {
  220. assert o <= (o + 8) via "a <= (a + b): 0 <= b"(b:8)
  221. // The final "8" is redundant semantically, but helps the
  222. // wuffs-c code generator recognize that both slices have the
  223. // same constant length, and hence produce efficient C code.
  224. this.output[o:o + 8].copy_from_slice!(s:this.suffixes[c][:8])
  225. if steps <= 0 {
  226. break
  227. }
  228. steps -= 1
  229. // This line is essentially "o -= 8". The "& 8191" is a no-op
  230. // in practice, but is necessary for the overflow checker.
  231. o = (o ~mod- 8) & 8191
  232. c = this.prefixes[c] as base.u32
  233. }
  234. first_byte = this.suffixes[c][0]
  235. if code == save_code {
  236. this.output[output_wi] = first_byte
  237. output_wi = (output_wi + 1) & 8191
  238. }
  239. if save_code <= 4095 {
  240. lm1_b = (this.lm1s[prev_code] ~mod+ 1) & 4095
  241. this.lm1s[save_code] = lm1_b
  242. if (lm1_b % 8) <> 0 {
  243. this.prefixes[save_code] = this.prefixes[prev_code]
  244. this.suffixes[save_code] = this.suffixes[prev_code]
  245. this.suffixes[save_code][lm1_b % 8] = first_byte
  246. } else {
  247. this.prefixes[save_code] = prev_code as base.u16
  248. this.suffixes[save_code][0] = first_byte as base.u8
  249. }
  250. save_code += 1
  251. if width < 12 {
  252. width += 1 & (save_code >> width)
  253. }
  254. prev_code = code
  255. }
  256. } else {
  257. this.read_from_return_value = 3
  258. break
  259. }
  260. // Flush the output if it could be too full to contain the entire
  261. // decoding of the next code. The longest possible decoding is slightly
  262. // less than 4096 and output's length is 8192, so a conservative
  263. // threshold is ensuring that output_wi <= 4095.
  264. if output_wi > 4095 {
  265. this.read_from_return_value = 1
  266. break
  267. }
  268. }
  269. // Rewind args.src, if we're not in "$short read" and we've read too many
  270. // bits.
  271. if this.read_from_return_value <> 2 {
  272. while n_bits >= 8 {
  273. n_bits -= 8
  274. if args.src.can_undo_byte() {
  275. args.src.undo_byte!()
  276. } else {
  277. this.read_from_return_value = 4
  278. break
  279. }
  280. }
  281. }
  282. this.save_code = save_code
  283. this.prev_code = prev_code
  284. this.width = width
  285. this.bits = bits
  286. this.n_bits = n_bits
  287. this.output_wi = output_wi
  288. }
  289. pri func decoder.write_to?(dst base.io_writer) {
  290. var s slice base.u8
  291. var n base.u64
  292. while this.output_wi > 0 {
  293. if this.output_ri > this.output_wi {
  294. return "#internal error: inconsistent I/O"
  295. }
  296. s = this.output[this.output_ri:this.output_wi]
  297. n = args.dst.copy_from_slice!(s:s)
  298. if n == s.length() {
  299. this.output_ri = 0
  300. this.output_wi = 0
  301. return ok
  302. }
  303. this.output_ri = (this.output_ri ~mod+ ((n & 0xFFFFFFFF) as base.u32)) & 8191
  304. yield? base."$short write"
  305. }
  306. }
  307. pub func decoder.flush!() slice base.u8 {
  308. var s slice base.u8
  309. if this.output_ri <= this.output_wi {
  310. s = this.output[this.output_ri:this.output_wi]
  311. }
  312. this.output_ri = 0
  313. this.output_wi = 0
  314. return s
  315. }