leb128.go

Documentation: github.com/tetratelabs/wazero/internal/leb128

     1  package leb128
     2  
     3  import (
     4  	"errors"
     5  	"fmt"
     6  	"io"
     7  )
     8  
     9  const (
    10  	maxVarintLen32 = 5
    11  	maxVarintLen33 = maxVarintLen32
    12  	maxVarintLen64 = 10
    13  
    14  	int33Mask  int64 = 1 << 7
    15  	int33Mask2       = ^int33Mask
    16  	int33Mask3       = 1 << 6
    17  	int33Mask4       = 8589934591 // 2^33-1
    18  	int33Mask5       = 1 << 32
    19  	int33Mask6       = int33Mask4 + 1 // 2^33
    20  
    21  	int64Mask3 = 1 << 6
    22  	int64Mask4 = ^0
    23  )
    24  
    25  var (
    26  	errOverflow32 = errors.New("overflows a 32-bit integer")
    27  	errOverflow33 = errors.New("overflows a 33-bit integer")
    28  	errOverflow64 = errors.New("overflows a 64-bit integer")
    29  )
    30  
    31  // EncodeInt32 encodes the signed value into a buffer in LEB128 format
    32  //
    33  // See https://en.wikipedia.org/wiki/LEB128#Encode_signed_integer
    34  func EncodeInt32(value int32) []byte {
    35  	return EncodeInt64(int64(value))
    36  }
    37  
    38  // EncodeInt64 encodes the signed value into a buffer in LEB128 format
    39  //
    40  // See https://en.wikipedia.org/wiki/LEB128#Encode_signed_integer
    41  func EncodeInt64(value int64) (buf []byte) {
    42  	for {
    43  		// Take 7 remaining low-order bits from the value into b.
    44  		b := uint8(value & 0x7f)
    45  		// Extract the sign bit.
    46  		s := uint8(value & 0x40)
    47  		value >>= 7
    48  
    49  		// The encoding unsigned numbers is simpler as it only needs to check if the value is non-zero to tell if there
    50  		// are more bits to encode. Signed is a little more complicated as you have to double-check the sign bit.
    51  		// If either case, set the high-order bit to tell the reader there are more bytes in this int.
    52  		if (value != -1 || s == 0) && (value != 0 || s != 0) {
    53  			b |= 0x80
    54  		}
    55  
    56  		// Append b into the buffer
    57  		buf = append(buf, b)
    58  		if b&0x80 == 0 {
    59  			break
    60  		}
    61  	}
    62  	return buf
    63  }
    64  
    65  // EncodeUint32 encodes the value into a buffer in LEB128 format
    66  //
    67  // See https://en.wikipedia.org/wiki/LEB128#Encode_unsigned_integer
    68  func EncodeUint32(value uint32) []byte {
    69  	return EncodeUint64(uint64(value))
    70  }
    71  
    72  // EncodeUint64 encodes the value into a buffer in LEB128 format
    73  //
    74  // See https://en.wikipedia.org/wiki/LEB128#Encode_unsigned_integer
    75  func EncodeUint64(value uint64) (buf []byte) {
    76  	// This is effectively a do/while loop where we take 7 bits of the value and encode them until it is zero.
    77  	for {
    78  		// Take 7 remaining low-order bits from the value into b.
    79  		b := uint8(value & 0x7f)
    80  		value = value >> 7
    81  
    82  		// If there are remaining bits, the value won't be zero: Set the high-
    83  		// order bit to tell the reader there are more bytes in this uint.
    84  		if value != 0 {
    85  			b |= 0x80
    86  		}
    87  
    88  		// Append b into the buffer
    89  		buf = append(buf, b)
    90  		if b&0x80 == 0 {
    91  			return buf
    92  		}
    93  	}
    94  }
    95  
    96  type nextByte func(i int) (byte, error)
    97  
    98  func DecodeUint32(r io.ByteReader) (ret uint32, bytesRead uint64, err error) {
    99  	return decodeUint32(func(_ int) (byte, error) { return r.ReadByte() })
   100  }
   101  
   102  func LoadUint32(buf []byte) (ret uint32, bytesRead uint64, err error) {
   103  	return decodeUint32(func(i int) (byte, error) {
   104  		if i >= len(buf) {
   105  			return 0, io.EOF
   106  		}
   107  		return buf[i], nil
   108  	})
   109  }
   110  
   111  func decodeUint32(next nextByte) (ret uint32, bytesRead uint64, err error) {
   112  	// Derived from https://github.com/golang/go/blob/go1.20/src/encoding/binary/varint.go
   113  	// with the modification on the overflow handling tailored for 32-bits.
   114  	var s uint32
   115  	for i := 0; i < maxVarintLen32; i++ {
   116  		b, err := next(i)
   117  		if err != nil {
   118  			return 0, 0, err
   119  		}
   120  		if b < 0x80 {
   121  			// Unused bits must be all zero.
   122  			if i == maxVarintLen32-1 && (b&0xf0) > 0 {
   123  				return 0, 0, errOverflow32
   124  			}
   125  			return ret | uint32(b)<<s, uint64(i) + 1, nil
   126  		}
   127  		ret |= (uint32(b) & 0x7f) << s
   128  		s += 7
   129  	}
   130  	return 0, 0, errOverflow32
   131  }
   132  
   133  func LoadUint64(buf []byte) (ret uint64, bytesRead uint64, err error) {
   134  	bufLen := len(buf)
   135  	if bufLen == 0 {
   136  		return 0, 0, io.EOF
   137  	}
   138  
   139  	// Derived from https://github.com/golang/go/blob/go1.20/src/encoding/binary/varint.go
   140  	var s uint64
   141  	for i := 0; i < maxVarintLen64; i++ {
   142  		if i >= bufLen {
   143  			return 0, 0, io.EOF
   144  		}
   145  		b := buf[i]
   146  		if b < 0x80 {
   147  			// Unused bits (non first bit) must all be zero.
   148  			if i == maxVarintLen64-1 && b > 1 {
   149  				return 0, 0, errOverflow64
   150  			}
   151  			return ret | uint64(b)<<s, uint64(i) + 1, nil
   152  		}
   153  		ret |= (uint64(b) & 0x7f) << s
   154  		s += 7
   155  	}
   156  	return 0, 0, errOverflow64
   157  }
   158  
   159  func DecodeInt32(r io.ByteReader) (ret int32, bytesRead uint64, err error) {
   160  	return decodeInt32(func(_ int) (byte, error) { return r.ReadByte() })
   161  }
   162  
   163  func LoadInt32(buf []byte) (ret int32, bytesRead uint64, err error) {
   164  	return decodeInt32(func(i int) (byte, error) {
   165  		if i >= len(buf) {
   166  			return 0, io.EOF
   167  		}
   168  		return buf[i], nil
   169  	})
   170  }
   171  
   172  func decodeInt32(next nextByte) (ret int32, bytesRead uint64, err error) {
   173  	var shift int
   174  	var b byte
   175  	for {
   176  		b, err = next(int(bytesRead))
   177  		if err != nil {
   178  			return 0, 0, fmt.Errorf("readByte failed: %w", err)
   179  		}
   180  		ret |= (int32(b) & 0x7f) << shift
   181  		shift += 7
   182  		bytesRead++
   183  		if b&0x80 == 0 {
   184  			if shift < 32 && (b&0x40) != 0 {
   185  				ret |= ^0 << shift
   186  			}
   187  			// Over flow checks.
   188  			// fixme: can be optimized.
   189  			if bytesRead > maxVarintLen32 {
   190  				return 0, 0, errOverflow32
   191  			} else if unused := b & 0b00110000; bytesRead == maxVarintLen32 && ret < 0 && unused != 0b00110000 {
   192  				return 0, 0, errOverflow32
   193  			} else if bytesRead == maxVarintLen32 && ret >= 0 && unused != 0x00 {
   194  				return 0, 0, errOverflow32
   195  			}
   196  			return
   197  		}
   198  	}
   199  }
   200  
   201  // DecodeInt33AsInt64 is a special cased decoder for wasm.BlockType which is encoded as a positive signed integer, yet
   202  // still needs to fit the 32-bit range of allowed indices. Hence, this is 33, not 32-bit!
   203  //
   204  // See https://webassembly.github.io/spec/core/binary/instructions.html#control-instructions
   205  func DecodeInt33AsInt64(r io.ByteReader) (ret int64, bytesRead uint64, err error) {
   206  	var shift int
   207  	var b int64
   208  	var rb byte
   209  	for shift < 35 {
   210  		rb, err = r.ReadByte()
   211  		if err != nil {
   212  			return 0, 0, fmt.Errorf("readByte failed: %w", err)
   213  		}
   214  		b = int64(rb)
   215  		ret |= (b & int33Mask2) << shift
   216  		shift += 7
   217  		bytesRead++
   218  		if b&int33Mask == 0 {
   219  			break
   220  		}
   221  	}
   222  
   223  	// fixme: can be optimized
   224  	if shift < 33 && (b&int33Mask3) == int33Mask3 {
   225  		ret |= int33Mask4 << shift
   226  	}
   227  	ret = ret & int33Mask4
   228  
   229  	// if 33rd bit == 1, we translate it as a corresponding signed-33bit minus value
   230  	if ret&int33Mask5 > 0 {
   231  		ret = ret - int33Mask6
   232  	}
   233  	// Over flow checks.
   234  	// fixme: can be optimized.
   235  	if bytesRead > maxVarintLen33 {
   236  		return 0, 0, errOverflow33
   237  	} else if unused := b & 0b00100000; bytesRead == maxVarintLen33 && ret < 0 && unused != 0b00100000 {
   238  		return 0, 0, errOverflow33
   239  	} else if bytesRead == maxVarintLen33 && ret >= 0 && unused != 0x00 {
   240  		return 0, 0, errOverflow33
   241  	}
   242  	return ret, bytesRead, nil
   243  }
   244  
   245  func DecodeInt64(r io.ByteReader) (ret int64, bytesRead uint64, err error) {
   246  	return decodeInt64(func(_ int) (byte, error) { return r.ReadByte() })
   247  }
   248  
   249  func LoadInt64(buf []byte) (ret int64, bytesRead uint64, err error) {
   250  	return decodeInt64(func(i int) (byte, error) {
   251  		if i >= len(buf) {
   252  			return 0, io.EOF
   253  		}
   254  		return buf[i], nil
   255  	})
   256  }
   257  
   258  func decodeInt64(next nextByte) (ret int64, bytesRead uint64, err error) {
   259  	var shift int
   260  	var b byte
   261  	for {
   262  		b, err = next(int(bytesRead))
   263  		if err != nil {
   264  			return 0, 0, fmt.Errorf("readByte failed: %w", err)
   265  		}
   266  		ret |= (int64(b) & 0x7f) << shift
   267  		shift += 7
   268  		bytesRead++
   269  		if b&0x80 == 0 {
   270  			if shift < 64 && (b&int64Mask3) == int64Mask3 {
   271  				ret |= int64Mask4 << shift
   272  			}
   273  			// Over flow checks.
   274  			// fixme: can be optimized.
   275  			if bytesRead > maxVarintLen64 {
   276  				return 0, 0, errOverflow64
   277  			} else if unused := b & 0b00111110; bytesRead == maxVarintLen64 && ret < 0 && unused != 0b00111110 {
   278  				return 0, 0, errOverflow64
   279  			} else if bytesRead == maxVarintLen64 && ret >= 0 && unused != 0x00 {
   280  				return 0, 0, errOverflow64
   281  			}
   282  			return
   283  		}
   284  	}
   285  }
   286
View as plain text