1. 개요
Little Endian Base 128, LEB128한정된 공간에 정수 또는 연속된 정수들을 저장할 때 사용하는 가변 길이 인코딩
2. 상세
흔히 컴퓨터에서 정수를 나타낼 때, 2의 거듭제곱 길이의 공간을 할당해 2진법으로 숫자를 저장한다.unsigned int, 리틀 엔디안을 예로 들면 1234를 저장할 때 우선 0b10011010010으로 변환되고, 이어서 나머지 32비트를 채우기 위해 0들을 붙여 0b0000 0000 0000 0000 0000 0100 1101 0010로 만들고, 이를 리틀 엔디안으로 메모리에 저장해 최종적으로 0b1101 0010 0000 0100 0000 0000 0000 0000이 된다.딱 보면 알겠지만 대부분의 일상적인 정수 범위(나이, 재고량, 온도 등)에서는 0으로 채워지는 공간 낭비가 심하다. 어차피 글자 하나도 몇 바이트씩 차지하는데 딱히 상관이 있나? 싶지만 이런 정수가 하나가 아니라 몇 십, 몇 백만 개 단위로 처리되는 분야에서는 꽤나 문제가 된다. 특히 메모리 안에서라면 [math(\mathcal O(1))] 접근을 위해 길이를 일정하게 맞추는(align) 것이 좋겠지만 파일에 저장할 때는 가급적 용량을 줄이는 것이 중요하므로 주로 대용량의 바이너리 데이터 저장 용도로 쓰인다.
앞선 비유에 첨언하자면
unsigned char와 같이 작은 자료형을 쓰는 것이 반드시 해결책이 될 수는 없다. 데이터 100만개 중 90%는 작은 값이고 10%만 아주 큰 범위의 값일 수 있기 때문이다. 또한 후술하듯이 제한 없이 임의 크기의 정수를 인코딩할 수 있어 아주 극단적이고 큰 값도 손실 없이 표현이 가능하다.이름의 128은 각 바이트에 더해지는 값이지, AES-128, UTF-X처럼 비트 갯수나 바이트 갯수가 아니다. 따라서 LEB128 외의 다른 변종은 없다. 빅 엔디안을 쓰는 BEB128역시 존재하지 않는다.
3. 과정
3.1. 부호 없는 정수
Unsigned LEB128, ULEB1281. 음이 아닌 정수 [math(n)]을 이진법으로 나타낸다.
1. 해당 이진수의 비트 길이가 7의 배수가 될 때까지 앞에 0을 붙힌다.
1. 해당 숫자를 비트 7개마다 나누어 한 바이트로 저장한다.
1. 각 바이트마다 [math(2^7)], 즉 128을
다시 말해 맨 앞의 비트(most significant bit)를 1로 바꾼다.
1. 단, 맨 앞 바이트에는 [math({\sim}2^7)], 즉 127을
다시 말해 맨 앞의 비트를 0으로 바꾼다.
1. 결과로 나온 바이트들의 순서를 뒤집는다.
1. 해당 이진수의 비트 길이가 7의 배수가 될 때까지 앞에 0을 붙힌다.
1. 해당 숫자를 비트 7개마다 나누어 한 바이트로 저장한다.
1. 각 바이트마다 [math(2^7)], 즉 128을
OR 연산한다.다시 말해 맨 앞의 비트(most significant bit)를 1로 바꾼다.
1. 단, 맨 앞 바이트에는 [math({\sim}2^7)], 즉 127을
AND 연산한다.다시 말해 맨 앞의 비트를 0으로 바꾼다.
1. 결과로 나온 바이트들의 순서를 뒤집는다.
128을
OR 연산한다고 되어 있지만 실제로 구현할 때는 0으로 초기화하고 128을 더해도 상관없다.예를 들어, 252601[1]을 ULEB128 인코딩하면 다음과 같다.
우선 이진법으로 나타내면
0b111101101010111001이며 길이가 18이니 0을 앞에 3개 붙여 21을 만든다. 이를 7개씩 나누면| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 000 1111 | 011 0101 | 011 1001 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| - | 0 | 0 | 0 | 1 | 1 | 1 | 1 | - | 0 | 1 | 1 | 0 | 1 | 0 | 1 | - | 0 | 1 | 1 | 1 | 0 | 0 | 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
이제 첫 바이트에는 맨 앞에 0을, 나머지 바이트에는 맨 앞에 1을 붙힌다.
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | |||
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
이제 리틀 엔디언이 되도록 바이트를 전부 역순으로 나열한다.
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
비트로는
0b101110011011010100001111, hex로는 0x B9 B5 0F인 3바이트로 인코딩 되었다.3.2. 부호 있는 정수
Signed LEB1281. 정수 [math(|n|)]을 이진법으로 나타낸다.
1. 해당 이진수의 비트 길이가 7의 배수가 될 때까지 앞에 0을 붙힌다.
1. [math(n)]이 음수일 경우, 2의 보수로 변환한다.
1. 해당 숫자를 비트 7개마다 나누어 한 바이트로 저장한다.
1. 각 바이트마다 [math(2^7)], 즉 128을
1. 단, 맨 앞 바이트에는 [math({\sim}2^7)], 즉 127을
1. 결과로 나온 바이트들의 순서를 뒤집는다.
1. 해당 이진수의 비트 길이가 7의 배수가 될 때까지 앞에 0을 붙힌다.
1. [math(n)]이 음수일 경우, 2의 보수로 변환한다.
1. 해당 숫자를 비트 7개마다 나누어 한 바이트로 저장한다.
1. 각 바이트마다 [math(2^7)], 즉 128을
OR 연산한다.1. 단, 맨 앞 바이트에는 [math({\sim}2^7)], 즉 127을
AND 연산한다.1. 결과로 나온 바이트들의 순서를 뒤집는다.
과정은 수동으로 2의 보수를 계산하는 부분을 빼면 상당히 유사하다. 이걸 직접 하는 이유는 LEB128이 가변 길이 인코딩이고, 정확히 어느 위치에 부호 비트가 들어갈지 알 수 없기 때문이다.
앞선 예시와 비슷하게, -2465[2]를 LEB128 인코딩하면 다음과 같다.
우선 절댓값인 2465를 이진법으로 나타내면
0b100110100001이며 길이가 12이니 0을 앞에 2개 붙여 14를 만든다. 음수를 만들기 위해 비트를 전부 반전하고 1을 더한다.| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
7개씩 나누고 첫 바이트에는 0을, 나머지 바이트에는 1을 붙히고 반전한다.
| 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | ||
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
비트로는
0b1101111101101100, hex로는 0x DF 6C인 2바이트로 인코딩되었다.3.3. 디코딩
디코딩은 인코딩 과정을 완전히 역순으로 따라하면 된다. 우선 맨 처음 비트가 1이면 뒤에 데이터가 더 있다는 뜻이므로1. 다음 바이트를 읽어와 맨 뒤 7비트를 버퍼에 역순으로 추가한다.
1. 만약 현재 바이트에 128을
1. 버퍼의 비트열을 2진법으로 해석한다.
1. 만약 현재 바이트에 128을
AND한 결과가 0보다 클 경우 1로 돌아간다.1. 버퍼의 비트열을 2진법으로 해석한다.
부호 있는 LEB128의 경우 3번 과정에서 음수 처리 역시 진행한다.
4. 특징
UTF-8과 비슷하게 가변 길이 인코딩인 만큼, 여러 장단점을 공유한다.가장 큰 장점은 상황에 따라 공간을 크게 절약할 수 있다는 것이다.
UTF-8과 비슷하게 상수 시간 인덱싱이 불가능하다. 가변 길이 인코딩 특성상 추가, 수정, 삭제 등등이 번거로워지기 때문에 저장 시에만 사용하고 실제로 쓰려면 디코딩해서 메모리에 올려야 한다.
5. 사용 분야
- DWARF 디버그 파일에 사용된다.
- xz 압축 파일