Lesson plan

BCJ (algorithm)

In data compression, BCJ, short for branch/call/jump, refers to a technique that improves the compression of machine code by replacing relative branch addresses with absolute ones. This allows a Lempel–Ziv compressor to identify duplicate targets and more efficiently encode them. On decompression, the inverse filter restores the original encoding. Different BCJ filters are used for different instruction sets, as each use different opcodes for branching. A form of BCJ is seen in Microsoft's cabinet file format from 1996, which filters x86 CALL instructions for the LZX compressor. The 7z and xz file formats implement BCJ for multiple architectures. ZPAQ calls its x86 BCJ as "E8E9", after the opcode values. bsdiff, a tool for delta updates, circumvents the need of writing architecture-specific BCJ tools by encoding bytewise differences. This allows it to be much better than the "match and copy" type tools such as VCDIFF, giving an output size of only 6% for Google Chrome. However, Google's courgette, which adds a layer of explicit disassembly, is able to produce 9× smaller diffs.

Back to article

Article summary

In data compression, BCJ, short for branch/call/jump, refers to a technique that improves the compression of machine code by replacing relative branch addresses with absolute ones. This allows a Lempel–Ziv compressor to identify duplicate targets and more efficiently encode them. On decompression, the inverse filter restores the original encoding. Different BCJ filters are used for different instruction sets, as each use different opcodes for branching. A form of BCJ is seen in Microsoft's cabinet file format from 1996, which filters x86 CALL instructions for the LZX compressor. The 7z and xz file formats implement BCJ for multiple architectures. ZPAQ calls its x86 BCJ as "E8E9", after the opcode values. bsdiff, a tool for delta updates, circumvents the need of writing architecture-specific BCJ tools by encoding bytewise differences. This allows it to be much better than the "match and copy" type tools such as VCDIFF, giving an output size of only 6% for Google Chrome. However, Google's courgette, which adds a layer of explicit disassembly, is able to produce 9× smaller diffs.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.