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