<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>libkate: Format - variable length integer</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.6.1 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</span></a></li>
<li class="current"><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="annotated.html"><span>Data Structures</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
<li><a href="examples.html"><span>Examples</span></a></li>
</ul>
</div>
</div>
<div class="contents">
<h1><a class="anchor" id="format_32v">Format - variable length integer </a></h1><p>Small integers are often needed, and the Kate bitstream format has a way to store them using a fraction of a byte to save space. This format is simple on purpose, and is not optimal. However, it allows easy compression of bitstreams using lots of small integers. All 32 bit integers may be represented by this encoding.</p>
<p>A variable length integer is stored in the following way:</p>
<ul>
<li>if the integer is between 0 and 14, it is stored as 4 bits directly representing the integer's value.</li>
<li>otherwise, it is stored as a first 4 bit value of 15, followed by a single bit for its sign (1 if negative, 0 if positive), then a 5 bit number representing one less than the number of bits needed to represent the absolute value of that number, followed by the absolute value of the number itself on the number of bits needed to represent it.</li>
</ul>
<p>A few examples:</p>
<ul>
<li>0 is stored as 0000 (4 bits)</li>
</ul>
<ul>
<li>-1 is stored as 1111 1 00001 1 (11 bits)</li>
</ul>
<ul>
<li>7 is stored as 0111 (4 bits)</li>
</ul>
<ul>
<li>17 is stored as 1111 0 00100 10001 (15 bits)</li>
</ul>
<ul>
<li>-3 is stored as 1111 1 00010 11 (12 bits)</li>
</ul>
<ul>
<li>1000 is stored as 1111 0 01001 11 1110 1000 (20 bits)</li>
</ul>
<ul>
<li>842389532 is stored as 1111 0 11101 0011 0010 0011 0101 1101 1000 0001 1100 (42 bits)</li>
</ul>
<p>Simple alterations would allow even more compression for typical numbers (eg, offsetting the numbers to allow -1 (a common occurence) to be stored on 4 bits, and noticing that the first bit of the bitstream stored last for large numbers is always 1), but are left for a possible future bitstream change as this would mean either an incompatible change, or a use for very few values, making the change almost pointless. </p>
</div>
<hr size="1"/><address style="text-align: right;"><small>Generated on Wed Dec 23 04:05:07 2009 for libkate by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.1 </small></address>
</body>
</html>
