Meta tags:

Headings (most frequently used words):

encoding, variable, length, integer, contents, applications, and, history, benefits, general, structure, variants, examples, references, group, varint, signed, numbers, removing, redundancy, sign, bit, zigzag, two, complement,

Text of the page (most frequently used words):
the (113), vlq (36), and (34), 00000000 (32), #variable (31), integer (30), encoding (29), #length (28), bit (23), octet (23), for (20), this (18), with (16), format (16), edit (16), numbers (16), integers (14), are (14), that (14), bits (13), significant (13), number (13), can (13), from (12), 11111111 (12), byte (12), used (12), values (11), value (11), such (11), encoded (11), use (10), more (10), negative (10), file (9), signed (9), least (9), first (9), using (8), octets (8), than (8), also (8), bytes (8), wikipedia (7), last (7), all (7), 128 (7), then (7), which (7), where (7), range (7), most (7), sign (7), retrieved (6), midi (6), 10000000 (6), quantity (6), have (6), representation (6), one (6), has (6), positive (6), general (6), page (5), articles (5), links (5), data (5), group (5), varint (5), large (5), rules (5), 01111111 (5), another (5), way (5), represent (5), base (5), example (5), 000 (5), there (5), each (5), redundancy (5), maximum (5), since (5), leb128 (5), encode (5), two (5), applications (5), contents (4), search (4), may (4), was (4), august (4), 2026 (4), references (4), pdf (4), information (4), specification (4), version (4), protocol (4), buffers (4), archived (4), unreal (4), 2020 (4), google (4), decimal (4), msb (4), other (4), 137 (4), its (4), only (4), instead (4), zero (4), complement (4), zigzag (4), follows (4), called (4), representations (4), unsigned (4), codes (4), endian (4), history (4), hide (4), move (4), sidebar (4), toggle (3), view (3), dead (3), wayback (3), short (3), compression (3), 2021 (3), system (3), dwarf (3), debugging (3), original (3), llvm (3), source (3), method (3), object (3), standard (3), asn (3), basic (3), 10000001 (3), 097 (3), binary (3), gives (3), examples (3), but (3), 0001 (3), whether (3), not (3), lowest (3), representing (3), notation (3), prepending (3), possible (3), particular (3), minimum (3), any (3), stream (3), arranged (3), uses (3), mapping (3), changes (3), fixed (3), chunk (3), structure (3), similar (3), gve (3), variants (3), typically (3), bound (3), represented (3), wordlength (3), smaller (3), ones (3), benefits (3), little (3), published (3), exist (3), tools (3), main (3), language (2), table (2), contact (2), about (2), privacy (2), policy (2), additional (2), terms (2), you (2), categories (2), external (2), lacking (2), reliable (2), description (2), wikidata (2), link (2), git (2), free (2), 1999 (2), packages (2), stoklund (2), 2019 (2), width (2), binaryreader (2), binarywriter (2), int (2), machine (2), oracle (2), portable (2), pof (2), 2011 (2), 6256 (2), rfc (2), doi (2), self (2), delimiting (2), numeric (2), protocols (2), 11000000 (2), 00100000 (2), 151 (2), 383 (2), 127 (2), hexadecimal (2), set (2), groups (2), thus (2), becomes (2), 1001 (2), added (2), very (2), starting (2), equivalent (2), here (2), uintvar (2), making (2), representable (2), vlqs (2), just (2), 0x80 (2), padding (2), removing (2), scheme (2), multiple (2), form (2), mapped (2), their (2), known (2), corresponds (2), etc (2), nonnegative (2), being (2), position (2), represents (2), compact (2), reserved (2), indicate (2), been (2), many (2), developed (2), cpu (2), branches (2), header (2), layout (2), need (2), remove (2), continuation (2), defined (2), various (2), commonly (2), chunks (2), much (2), same (2), inherent (2), longer (2), fewer (2), support (2), size (2), defines (2), abstract (2), syntax (2), 1983 (2), later (2), formats (2), unless (2), application (2), variations (2), larger (2), appearance (2), upload (2), read (2), article (2), log (2), create (2), account (2), donate (2), menu (2), add, topic, mobile, cookie, statement, statistics, developers, code, conduct, legal, safety, contacts, disclaimers, text, available, under, apply, site, agree, registered, trademark, non, profit, organization, wikimedia, foundation, inc, creative, commons, attribution, sharealike, license, rendered, parsoid, edited, utc, hidden, webarchive, template, different, lossless, algorithms, types, https, org, index, php, title, length_integer, oldid, 1367364674, length_quantity, spec, october, fast, scalable, distributed, revision, control, standards, december, 2005, 2009, 2010, olesen, jakob, november, july, jeff, dean, challenges, building, scale, retrieval, systems, accessed, bitcode, section, introduction, javascript, maps, read7bitencodedint, write7bitencodedint, 2013, welcome, website, informational, eddy, wesley, davies, elwyn, 2070, 1721, issn, 17487, rfc6256, internet, research, task, force, february, international, telecommunication, union, itu, recommendation, 690, iso, iec, 8825, technology, ber, canonical, cer, distinguished, der, unreliable, quantities, jianguo, wang, chunbin, lin, yannis, papakonstantinou, steven, swanson, 2017, 1145, 3035918, 3064007, experimental, study, bitmap, inverted, list, 0fffffff, 00001111, 268, 455, 435, 08000000, 00001000, 134, 728, 217, 00200000, 152, 001fffff, 00011111, 00004000, 01000000, 384, 00003fff, 00111111, 00002000, 8192, 00000080, 0000007f, look, digit, our, boldface, something, these, denote, follow, definition, will, take, comes, break, 0000001, 0001001, 10001001, worked, out, diagram, showing, how, convert, 106, 903, bijective, numeration, however, removes, extends, shorter, adding, offset, exactly, store, 0x8000, assigned, conversely, 0xff7f, similarly, 0x808000, means, 0xffff7f, 663, 113, 512, 511, described, above, simply, 358, 0x8266, 0358, 0x808266, 00358, 0x80808266, forth, start, input, proceeds, usual, extended, odd, fills, xoring, turns, subtracts, remember, multiplied, 1xxx, multiples, alternative, notably, done, 100, counting, alternates, between, step, hence, whence, name, concretely, transform, effect, indices, difference, seventh, consecutive, engine, handled, needs, present, prefixvarint, design, uint64, said, invented, times, independently, changed, into, chained, infinitely, continuations, after, observing, traditional, incurs, during, decompression, single, uint32, storage, following, uint32s, eliminates, check, copied, directly, destination, faster, modern, pipelined, cpus, reduces, simple, somewhat, redundant, handle, techniques, 0x00, 0x7f, assumes, simpler, decode, whole, require, oriented, manipulation, decoding, huffman, time, arbitrarily, unlike, words, long, upper, contrast, would, either, inadequate, too, encountered, small, results, average, primary, compactness, flexibility, principle, documentation, describes, field, consisting, payload, extensively, web, browsers, contain, lot, line, column, mappings, keep, map, tag, 1984, now, obsolete, environment, introduced, issued, refers, delay, tolerant, networking, variant, effectively, analog, does, classes, net, framework, microsoft, uleb128, sdnv, wap, identifiers, 2001, extensible, music, xmf, names, encint, vbyte, vint, methods, some, built, necessary, prohibited, prohibiting, certain, leading, trailing, several, early, versions, variation, big, important, able, common, sequence, needed, depends, magnitudes, expressed, imposed, schemes, confused, arbitrary, precision, arithmetic, redirected, encyclopedia, item, projects, printable, download, print, export, switch, legacy, parser, get, shortened, url, cite, permanent, related, what, actions, english, talk, 日本語, subsection, top, personal, special, pages, recent, community, portal, learn, help, contribute, random, current, events, navigation, jump, content,

Text of the page (random words):
donate create account log in personal tools donate create account log in contents move to sidebar hide top 1 applications and history 2 benefits 3 general structure 4 variants toggle variants subsection 4 1 group varint encoding 4 2 signed numbers 4 2 1 sign bit 4 2 2 zigzag encoding 4 2 3 two s complement 4 3 removing redundancy 5 examples 6 references toggle the table of contents variable length integer 1 language 日本語 edit links article talk english read edit view history tools tools move to sidebar hide actions read edit view history general what links here related changes upload file permanent link page information cite this page get shortened url switch to legacy parser print export download as pdf printable version in other projects wikidata item appearance move to sidebar hide from wikipedia the free encyclopedia redirected from variable length quantity encoding method for variable length integers not to be confused with arbitrary precision arithmetic a variable length integer is a variable length encoded representation of an integer value using a sequence of bytes the number of bytes that is needed depends on the value being represented with larger magnitudes using more bytes than smaller ones a variable length integer has no inherent bound on the range of values that can be expressed unless such a bound is imposed in a particular application such schemes have been in use in applications at least since the 1983 specification of the midi file format variations exist for representing signed and unsigned integers variable length integers are used in applications where it is important to be able to support a large range of integer values and in which smaller numbers are more common than larger ones several variations of such formats exist early versions used in the midi file format and abstract syntax notation one asn 1 used big endian representation a later developed little endian variation is called leb128 most variable length integer representation methods have some built in redundancy such that values can be represented using more bytes than necessary unless the longer representations are prohibited in a particular application e g by prohibiting certain leading or trailing byte values applications and history edit various names exist for formats encoding variable length integers such as varint vint vb variable byte vbyte encint etc 1 a variable length quantity vlq was defined for use in the standard midi file format 2 version 1 0 of which was published in 1983 it is also used in the later extensible music format xmf first published in 2001 base 128 is also used in the basic encoding rules of abstract syntax notation one asn 1 to encode tag numbers and object identifiers first published in 1984 3 it is also used in the now obsolete wap environment introduced in 1999 where it is called variable length unsigned integer or uintvar rfc 6256 issued in may 2011 defines the same format and refers to it as a self delimiting numeric value sdnv for use in delay tolerant networking protocols 4 the dwarf debugging format 5 defines a variant called leb128 or uleb128 for unsigned numbers where the least significant group of 7 bits is encoded in the first byte and the most significant bits are in the last byte so it is effectively the little endian analog of a vlq google protocol buffers use a similar format to have compact representation of integer values 6 as does oracle portable object format pof 7 and the microsoft net framework 7 bit encoded int in the binaryreader and binarywriter classes 8 it is also used extensively in web browsers for source mapping which contain a lot of integer line and column number mappings to keep the size of the map to a minimum 9 variable width integers in llvm use a similar principle the encoding chunks are little endian and need not be 8 bits in size the llvm documentation describes a field that uses 4 bit chunk with each chunk consisting of 1 bit continuation and 3 bits payload 10 benefits edit the primary benefits of variable length integer encoding are its compactness and its flexibility to support any range of values in most applications smaller integers are more commonly encountered than very large ones with variable length integer encoding small numbers use fewer bytes which typically results in using fewer bytes on average if a large quantity of integer values are encoded this way at the same time variable length integer encoding can also represent arbitrarily large integers unlike fixed wordlength representations such as 8 bit bytes 16 bit words 32 bit integers or 64 bit long integers there is no inherent upper bound on the range of values that can be represented by a variable length integer encoding in contrast fixed length integer representations would typically have either an inadequate range of representable values if a short wordlength is used or can use too much data to represent each integer if a longer wordlength is used variable length integer encoding is also simpler to encode and decode than most other variable length codes such as huffman codes since vlq codes use whole byte chunks of data more general variable length codes typically require much more bit oriented manipulation for encoding and decoding general structure edit the encoding assumes an octet an 8 bit byte where the most significant bit msb also commonly known as the sign bit is reserved to indicate whether another vlq octet follows vlq octet 7 6 5 4 3 2 1 0 2 7 2 6 2 5 2 4 2 3 2 2 2 1 2 0 a b n if a is 0 then this is the last vlq octet of the integer if a is 1 then another vlq octet follows b is a 7 bit number 0x00 0x7f and n is the position of the vlq octet where b 0 is the least significant the vlq octets are arranged most significant first in a stream variants edit the general vlq encoding is simple but in basic form is only defined for unsigned integers nonnegative positive or zero and is somewhat redundant since prepending 0x80 octets corresponds to zero padding there are various signed number representations to handle negative numbers and techniques to remove the redundancy group varint encoding edit google developed group varint encoding gve after observing that traditional vlq encoding incurs many cpu branches during decompression gve uses a single byte as a header for 4 variable length uint32 values the header byte has 4 2 bit numbers representing the storage length of each of the following 4 uint32s such a layout eliminates the need to check and remove vlq continuation bits data bytes can be copied directly to their destination this layout reduces cpu branches making gve faster than vlq on modern pipelined cpus 11 prefixvarint is a similar design but with a uint64 maximum it is said to have been invented multiple times independently 12 it is possible to be changed into a chained version with infinitely many continuations signed numbers edit sign bit edit negative numbers can be handled using a sign bit which only needs to be present in the first octet in the data format for unreal packages used by the unreal engine a variable length quantity scheme called compact indices 13 is used the only difference in this encoding is that the first vlq octet has the seventh bit reserved to indicate whether the encoded integer is positive or negative any consecutive vlq octet follows the general structure unreal signed vlq first vlq octet other vlq octets 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 2 7 2 6 2 5 2 4 2 3 2 2 2 1 2 0 2 7 2 6 2 5 2 4 2 3 2 2 2 1 2 0 s a b 0 a b n n 0 if s is 0 then the vlq represents a positive integer if s is 1 then the vlq represents a negative number if a is 0 then this is the last vlq octet of the integer if a is 1 then another vlq octet follows b is the number chunk being encoded and n is the position of the vlq octet where b 0 is the least significant the vlq octets are arranged least significant first in a stream zigzag encoding edit an alternative way to encode negative numbers is to use the least significant bit for sign this is notably done for google protocol buffers and is known as a zigzag encoding for signed integers 14 one can encode the numbers so that encoded 0 corresponds to 0 1 to 1 10 to 1 11 to 2 100 to 2 etc counting up alternates between nonnegative starting at 0 and negative since each step changes the least significant bit hence the sign whence the name zigzag encoding concretely transform the integer as n 1 n k 1 for fixed k bit integers this has the effect of mapping positive numbers to their multiples of two n 1 is equivalent of n x 2 example 0 1 2 3 are mapped to 0 2 4 6 mapping negative numbers to the positive odd numbers a 32 bit negative integer has a form of 1xxx so n 31 fills all the bits with 1 xoring a two s complement negative number with all 1 s turns it positive and subtracts 1 and remember that we multiplied the original number by 2 using n 1 so 1 2 3 are mapped to 1 3 5 two s complement edit leb128 uses two s complement to represent signed numbers in this scheme of representation n bits encode a range from 2 n to 2 n 1 and all negative numbers start with a 1 in the most significant bit in signed leb128 the input is sign extended so that its length is a multiple of 7 bits from there the encoding proceeds as usual 15 in leb128 the stream is arranged least significant first 15 removing redundancy edit with the vlq encoding described above any number that can be encoded with n octets can also be encoded with more than n octets simply by prepending additional 0x80 octets as zero padding for example the decimal number 358 can be encoded as the 2 octet vlq 0x8266 or the number 0358 can be encoded as 3 octet vlq 0x808266 or 00358 as the 4 octet vlq 0x80808266 and so forth however the vlq format used in git 16 removes this prepending redundancy and extends the representable range of shorter vlqs by adding an offset to vlqs of 2 or more octets in such a way that the lowest possible value for such an n 1 octet vlq becomes exactly one more than the maximum possible value for an n octet vlq in particular since a 1 octet vlq can store a maximum value of 127 the minimum 2 octet vlq 0x8000 is assigned the value 128 instead of 0 conversely the maximum value of such a 2 octet vlq 0xff7f is 16 511 instead of just 16 383 similarly the minimum 3 octet vlq 0x808000 has a value of 16 512 instead of zero which means that the maximum 3 octet vlq 0xffff7f is 2 113 663 instead of just 2 097 151 in this way there is one and only one encoding of each integer making this a base 128 bijective numeration examples edit diagram showing how to convert 106 903 from decimal to uintvar representation here is a worked out example for the decimal number 137 represent the value in binary notation e g 137 as 10001001 break it up in groups of 7 bits starting from the lowest significant bit e g 137 as 0000001 0001001 this is equivalent to representing the number in base 128 take the lowest 7 bits and that gives you the least significant byte 0 000 1001 this byte comes last for all the other groups of 7 bits in the example this is 000 0001 set the msb to 1 which gives 1 000 0001 in our example thus 137 becomes 1 000 0001 0 000 1001 where the bits in boldface are something we added these added bits denote whether there is another byte to follow or not thus by definition the very last byte of a variable length integer will have 0 as its msb another way to look at this is to represent the value in base 128 and then set the msb of all but the last base 128 digit to 1 the standard midi file format specification gives more examples 2 17 integer decimal integer binary variable length quantity binary integer hexadecimal variable length quantity hexadecimal 0 00000000 00000000 00000000 00000000 00000000 00000000 00 127 00000000 00000000 00000000 01111111 01111111 0000007f 7f 128 00000000 00000000 00000000 10000000 10000001 00000000 00000080 81 00 8192 00000000 00000000 00100000 00000000 11000000 00000000 00002000 c0 00 16 383 00000000 00000000 00111111 11111111 11111111 01111111 00003fff ff 7f 16 384 00000000 00000000 01000000 00000000 10000001 10000000 00000000 00004000 81 80 00 2 097 151 00000000 00011111 11111111 11111111 11111111 11111111 01111111 001fffff ff ff 7f 2 097 152 00000000 00100000 00000000 00000000 10000001 10000000 10000000 00000000 00200000 81 80 80 00 134 217 728 00001000 00000000 00000000 00000000 11000000 10000000 10000000 00000000 08000000 c0 80 80 00 268 435 455 00001111 11111111 11111111 11111111 11111111 11111111 11111111 01111111 0fffffff ff ff ff 7f references edit jianguo wang chunbin lin yannis papakonstantinou steven swanson an experimental study of bitmap compression vs inverted list compression archived 2019 12 07 at the wayback machine 2017 doi 10 1145 3035918 3064007 1 2 midi file format variable quantities unreliable source itu t recommendation x 690 iso iec 8825 1 information technology asn 1 encoding rules specification of basic encoding rules ber canonical encoding rules cer and distinguished encoding rules der international telecommunication union february 2021 eddy wesley m davies elwyn may 2011 using self delimiting numeric values in protocols internet research task force doi 10 17487 rfc6256 issn 2070 1721 rfc 6256 informational welcome to the dwarf debugging standard website retrieved 2 august 2026 google protocol buffers oracle portable object format pof archived 2013 12 27 at the wayback machine system io binarywriter write7bitencodedint int method and system io binaryreader read7bitencodedint method introduction to javascript source maps llvm bitcode file format section variable width integers accessed 2019 10 01 jeff dean challenges in building large scale information retrieval systems pdf p 58 retrieved 2020 05 30 olesen jakob stoklund 31 may 2020 stoklund varint archived from the original on 19 november 2020 retrieved 9 july 2020 unreal packages 1999 07 21 archived from the original on 2010 08 20 retrieved 2021 08 29 protocol buffers encoding signed integers 1 2 free standards group december 2005 dwarf debugging information format specification version 3 0 pdf p 70 retrieved 2009 07 19 git fast scalable distributed revision control system 28 october 2021 midi file format spec 1 1 pdf dead link retrieved from https en wikipedia org w index php title variable length_integer oldid 1367364674 variable length_quantity categories data types lossless compression algorithms hidden categories articles with short description short description is different from wikidata webarchive template wayback links all articles lacking reliable references articles lacking reliable references from august 2026 all articles with dead external links articles with dead external links from august 2026 this page was last edited on 2 august 2026 at 17 26 utc page was rendered with parsoid text is available under the creative commons attribution sharealike 4 0 license additional terms may apply by using this site you agree to the terms of use and privacy policy wikipedia is a register...