...
Run Format

Source file src/syscall/unzip_nacl.go

Documentation: syscall

  // Copyright 2009 The Go Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style
  // license that can be found in the LICENSE file.
  
  // Small in-memory unzip implementation.
  // A simplified copy of the pre-Go 1 compress/flate/inflate.go
  // and a modified copy of the zip reader in package time.
  // (The one in package time does not support decompression; this one does.)
  
  package syscall
  
  const (
  	maxCodeLen = 16    // max length of Huffman code
  	maxHist    = 32768 // max history required
  	maxLit     = 286
  	maxDist    = 32
  	numCodes   = 19 // number of codes in Huffman meta-code
  )
  
  type decompressor struct {
  	in  string // compressed input
  	out []byte // uncompressed output
  	b   uint32 // input bits, at top of b
  	nb  uint
  	err bool // invalid input
  	eof bool // reached EOF
  
  	h1, h2   huffmanDecoder        // decoders for literal/length, distance
  	bits     [maxLit + maxDist]int // lengths defining Huffman codes
  	codebits [numCodes]int
  }
  
  func (f *decompressor) nextBlock() {
  	for f.nb < 1+2 {
  		if f.moreBits(); f.err {
  			return
  		}
  	}
  	f.eof = f.b&1 == 1
  	f.b >>= 1
  	typ := f.b & 3
  	f.b >>= 2
  	f.nb -= 1 + 2
  	switch typ {
  	case 0:
  		f.dataBlock()
  	case 1:
  		// compressed, fixed Huffman tables
  		f.huffmanBlock(&fixedHuffmanDecoder, nil)
  	case 2:
  		// compressed, dynamic Huffman tables
  		if f.readHuffman(); f.err {
  			break
  		}
  		f.huffmanBlock(&f.h1, &f.h2)
  	default:
  		// 3 is reserved.
  		f.err = true
  	}
  }
  
  // RFC 1951 section 3.2.7.
  // Compression with dynamic Huffman codes
  
  var codeOrder = [...]int{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}
  
  func (f *decompressor) readHuffman() {
  	// HLIT[5], HDIST[5], HCLEN[4].
  	for f.nb < 5+5+4 {
  		if f.moreBits(); f.err {
  			return
  		}
  	}
  	nlit := int(f.b&0x1F) + 257
  	f.b >>= 5
  	ndist := int(f.b&0x1F) + 1
  	f.b >>= 5
  	nclen := int(f.b&0xF) + 4
  	f.b >>= 4
  	f.nb -= 5 + 5 + 4
  
  	// (HCLEN+4)*3 bits: code lengths in the magic codeOrder order.
  	for i := 0; i < nclen; i++ {
  		for f.nb < 3 {
  			if f.moreBits(); f.err {
  				return
  			}
  		}
  		f.codebits[codeOrder[i]] = int(f.b & 0x7)
  		f.b >>= 3
  		f.nb -= 3
  	}
  	for i := nclen; i < len(codeOrder); i++ {
  		f.codebits[codeOrder[i]] = 0
  	}
  	if !f.h1.init(f.codebits[0:]) {
  		f.err = true
  		return
  	}
  
  	// HLIT + 257 code lengths, HDIST + 1 code lengths,
  	// using the code length Huffman code.
  	for i, n := 0, nlit+ndist; i < n; {
  		x := f.huffSym(&f.h1)
  		if f.err {
  			return
  		}
  		if x < 16 {
  			// Actual length.
  			f.bits[i] = x
  			i++
  			continue
  		}
  		// Repeat previous length or zero.
  		var rep int
  		var nb uint
  		var b int
  		switch x {
  		default:
  			f.err = true
  			return
  		case 16:
  			rep = 3
  			nb = 2
  			if i == 0 {
  				f.err = true
  				return
  			}
  			b = f.bits[i-1]
  		case 17:
  			rep = 3
  			nb = 3
  			b = 0
  		case 18:
  			rep = 11
  			nb = 7
  			b = 0
  		}
  		for f.nb < nb {
  			if f.moreBits(); f.err {
  				return
  			}
  		}
  		rep += int(f.b & uint32(1<<nb-1))
  		f.b >>= nb
  		f.nb -= nb
  		if i+rep > n {
  			f.err = true
  			return
  		}
  		for j := 0; j < rep; j++ {
  			f.bits[i] = b
  			i++
  		}
  	}
  
  	if !f.h1.init(f.bits[0:nlit]) || !f.h2.init(f.bits[nlit:nlit+ndist]) {
  		f.err = true
  		return
  	}
  }
  
  // Decode a single Huffman block from f.
  // hl and hd are the Huffman states for the lit/length values
  // and the distance values, respectively. If hd == nil, using the
  // fixed distance encoding associated with fixed Huffman blocks.
  func (f *decompressor) huffmanBlock(hl, hd *huffmanDecoder) {
  	for {
  		v := f.huffSym(hl)
  		if f.err {
  			return
  		}
  		var n uint // number of bits extra
  		var length int
  		switch {
  		case v < 256:
  			f.out = append(f.out, byte(v))
  			continue
  		case v == 256:
  			// Done with huffman block; read next block.
  			return
  		// otherwise, reference to older data
  		case v < 265:
  			length = v - (257 - 3)
  			n = 0
  		case v < 269:
  			length = v*2 - (265*2 - 11)
  			n = 1
  		case v < 273:
  			length = v*4 - (269*4 - 19)
  			n = 2
  		case v < 277:
  			length = v*8 - (273*8 - 35)
  			n = 3
  		case v < 281:
  			length = v*16 - (277*16 - 67)
  			n = 4
  		case v < 285:
  			length = v*32 - (281*32 - 131)
  			n = 5
  		default:
  			length = 258
  			n = 0
  		}
  		if n > 0 {
  			for f.nb < n {
  				if f.moreBits(); f.err {
  					return
  				}
  			}
  			length += int(f.b & uint32(1<<n-1))
  			f.b >>= n
  			f.nb -= n
  		}
  
  		var dist int
  		if hd == nil {
  			for f.nb < 5 {
  				if f.moreBits(); f.err {
  					return
  				}
  			}
  			dist = int(reverseByte[(f.b&0x1F)<<3])
  			f.b >>= 5
  			f.nb -= 5
  		} else {
  			if dist = f.huffSym(hd); f.err {
  				return
  			}
  		}
  
  		switch {
  		case dist < 4:
  			dist++
  		case dist >= 30:
  			f.err = true
  			return
  		default:
  			nb := uint(dist-2) >> 1
  			// have 1 bit in bottom of dist, need nb more.
  			extra := (dist & 1) << nb
  			for f.nb < nb {
  				if f.moreBits(); f.err {
  					return
  				}
  			}
  			extra |= int(f.b & uint32(1<<nb-1))
  			f.b >>= nb
  			f.nb -= nb
  			dist = 1<<(nb+1) + 1 + extra
  		}
  
  		// Copy [-dist:-dist+length] into output.
  		// Encoding can be prescient, so no check on length.
  		if dist > len(f.out) {
  			f.err = true
  			return
  		}
  
  		p := len(f.out) - dist
  		for i := 0; i < length; i++ {
  			f.out = append(f.out, f.out[p])
  			p++
  		}
  	}
  }
  
  // Copy a single uncompressed data block from input to output.
  func (f *decompressor) dataBlock() {
  	// Uncompressed.
  	// Discard current half-byte.
  	f.nb = 0
  	f.b = 0
  
  	if len(f.in) < 4 {
  		f.err = true
  		return
  	}
  
  	buf := f.in[:4]
  	f.in = f.in[4:]
  	n := int(buf[0]) | int(buf[1])<<8
  	nn := int(buf[2]) | int(buf[3])<<8
  	if uint16(nn) != uint16(^n) {
  		f.err = true
  		return
  	}
  
  	if len(f.in) < n {
  		f.err = true
  		return
  	}
  	f.out = append(f.out, f.in[:n]...)
  	f.in = f.in[n:]
  }
  
  func (f *decompressor) moreBits() {
  	if len(f.in) == 0 {
  		f.err = true
  		return
  	}
  	c := f.in[0]
  	f.in = f.in[1:]
  	f.b |= uint32(c) << f.nb
  	f.nb += 8
  }
  
  // Read the next Huffman-encoded symbol from f according to h.
  func (f *decompressor) huffSym(h *huffmanDecoder) int {
  	for n := uint(h.min); n <= uint(h.max); n++ {
  		lim := h.limit[n]
  		if lim == -1 {
  			continue
  		}
  		for f.nb < n {
  			if f.moreBits(); f.err {
  				return 0
  			}
  		}
  		v := int(f.b & uint32(1<<n-1))
  		v <<= 16 - n
  		v = int(reverseByte[v>>8]) | int(reverseByte[v&0xFF])<<8 // reverse bits
  		if v <= lim {
  			f.b >>= n
  			f.nb -= n
  			return h.codes[v-h.base[n]]
  		}
  	}
  	f.err = true
  	return 0
  }
  
  var reverseByte = [256]byte{
  	0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
  	0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
  	0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
  	0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
  	0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
  	0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
  	0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
  	0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
  	0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
  	0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
  	0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
  	0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
  	0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
  	0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
  	0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
  	0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
  	0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
  	0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
  	0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
  	0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
  	0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
  	0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
  	0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
  	0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
  	0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
  	0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
  	0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
  	0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
  	0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
  	0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
  	0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
  	0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
  }
  
  // Hard-coded Huffman tables for DEFLATE algorithm.
  // See RFC 1951, section 3.2.6.
  var fixedHuffmanDecoder = huffmanDecoder{
  	7, 9,
  	[maxCodeLen + 1]int{7: 23, 199, 511},
  	[maxCodeLen + 1]int{7: 0, 24, 224},
  	[]int{
  		// length 7: 256-279
  		256, 257, 258, 259, 260, 261, 262,
  		263, 264, 265, 266, 267, 268, 269,
  		270, 271, 272, 273, 274, 275, 276,
  		277, 278, 279,
  
  		// length 8: 0-143
  		0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
  		12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
  		22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
  		32, 33, 34, 35, 36, 37, 38, 39, 40, 41,
  		42, 43, 44, 45, 46, 47, 48, 49, 50, 51,
  		52, 53, 54, 55, 56, 57, 58, 59, 60, 61,
  		62, 63, 64, 65, 66, 67, 68, 69, 70, 71,
  		72, 73, 74, 75, 76, 77, 78, 79, 80, 81,
  		82, 83, 84, 85, 86, 87, 88, 89, 90, 91,
  		92, 93, 94, 95, 96, 97, 98, 99, 100,
  		101, 102, 103, 104, 105, 106, 107, 108,
  		109, 110, 111, 112, 113, 114, 115, 116,
  		117, 118, 119, 120, 121, 122, 123, 124,
  		125, 126, 127, 128, 129, 130, 131, 132,
  		133, 134, 135, 136, 137, 138, 139, 140,
  		141, 142, 143,
  
  		// length 8: 280-287
  		280, 281, 282, 283, 284, 285, 286, 287,
  
  		// length 9: 144-255
  		144, 145, 146, 147, 148, 149, 150, 151,
  		152, 153, 154, 155, 156, 157, 158, 159,
  		160, 161, 162, 163, 164, 165, 166, 167,
  		168, 169, 170, 171, 172, 173, 174, 175,
  		176, 177, 178, 179, 180, 181, 182, 183,
  		184, 185, 186, 187, 188, 189, 190, 191,
  		192, 193, 194, 195, 196, 197, 198, 199,
  		200, 201, 202, 203, 204, 205, 206, 207,
  		208, 209, 210, 211, 212, 213, 214, 215,
  		216, 217, 218, 219, 220, 221, 222, 223,
  		224, 225, 226, 227, 228, 229, 230, 231,
  		232, 233, 234, 235, 236, 237, 238, 239,
  		240, 241, 242, 243, 244, 245, 246, 247,
  		248, 249, 250, 251, 252, 253, 254, 255,
  	},
  }
  
  // Huffman decoder is based on
  // J. Brian Connell, ``A Huffman-Shannon-Fano Code,''
  // Proceedings of the IEEE, 61(7) (July 1973), pp 1046-1047.
  type huffmanDecoder struct {
  	// min, max code length
  	min, max int
  
  	// limit[i] = largest code word of length i
  	// Given code v of length n,
  	// need more bits if v > limit[n].
  	limit [maxCodeLen + 1]int
  
  	// base[i] = smallest code word of length i - seq number
  	base [maxCodeLen + 1]int
  
  	// codes[seq number] = output code.
  	// Given code v of length n, value is
  	// codes[v - base[n]].
  	codes []int
  }
  
  // Initialize Huffman decoding tables from array of code lengths.
  func (h *huffmanDecoder) init(bits []int) bool {
  	// Count number of codes of each length,
  	// compute min and max length.
  	var count [maxCodeLen + 1]int
  	var min, max int
  	for _, n := range bits {
  		if n == 0 {
  			continue
  		}
  		if min == 0 || n < min {
  			min = n
  		}
  		if n > max {
  			max = n
  		}
  		count[n]++
  	}
  	if max == 0 {
  		return false
  	}
  
  	h.min = min
  	h.max = max
  
  	// For each code range, compute
  	// nextcode (first code of that length),
  	// limit (last code of that length), and
  	// base (offset from first code to sequence number).
  	code := 0
  	seq := 0
  	var nextcode [maxCodeLen]int
  	for i := min; i <= max; i++ {
  		n := count[i]
  		nextcode[i] = code
  		h.base[i] = code - seq
  		code += n
  		seq += n
  		h.limit[i] = code - 1
  		code <<= 1
  	}
  
  	// Make array mapping sequence numbers to codes.
  	if len(h.codes) < len(bits) {
  		h.codes = make([]int, len(bits))
  	}
  	for i, n := range bits {
  		if n == 0 {
  			continue
  		}
  		code := nextcode[n]
  		nextcode[n]++
  		seq := code - h.base[n]
  		h.codes[seq] = i
  	}
  	return true
  }
  
  func inflate(in string) (out []byte) {
  	var d decompressor
  	d.in = in
  	for !d.err && !d.eof {
  		d.nextBlock()
  	}
  	if len(d.in) != 0 {
  		println("fs unzip: junk at end of compressed data")
  		return nil
  	}
  	return d.out
  }
  
  // get4 returns the little-endian 32-bit value in b.
  func zget4(b string) int {
  	if len(b) < 4 {
  		return 0
  	}
  	return int(b[0]) | int(b[1])<<8 | int(b[2])<<16 | int(b[3])<<24
  }
  
  // get2 returns the little-endian 16-bit value in b.
  func zget2(b string) int {
  	if len(b) < 2 {
  		return 0
  	}
  	return int(b[0]) | int(b[1])<<8
  }
  
  func unzip(data string) {
  	const (
  		zecheader   = 0x06054b50
  		zcheader    = 0x02014b50
  		ztailsize   = 22
  		zheadersize = 30
  		zheader     = 0x04034b50
  	)
  
  	buf := data[len(data)-ztailsize:]
  	n := zget2(buf[10:])
  	size := zget4(buf[12:])
  	off := zget4(buf[16:])
  
  	hdr := data[off : off+size]
  	for i := 0; i < n; i++ {
  		// zip entry layout:
  		//	0	magic[4]
  		//	4	madevers[1]
  		//	5	madeos[1]
  		//	6	extvers[1]
  		//	7	extos[1]
  		//	8	flags[2]
  		//	10	meth[2]
  		//	12	modtime[2]
  		//	14	moddate[2]
  		//	16	crc[4]
  		//	20	csize[4]
  		//	24	uncsize[4]
  		//	28	namelen[2]
  		//	30	xlen[2]
  		//	32	fclen[2]
  		//	34	disknum[2]
  		//	36	iattr[2]
  		//	38	eattr[4]
  		//	42	off[4]
  		//	46	name[namelen]
  		//	46+namelen+xlen+fclen - next header
  		//
  		if zget4(hdr) != zcheader {
  			println("fs unzip: bad magic")
  			break
  		}
  		meth := zget2(hdr[10:])
  		mtime := zget2(hdr[12:])
  		mdate := zget2(hdr[14:])
  		csize := zget4(hdr[20:])
  		size := zget4(hdr[24:])
  		namelen := zget2(hdr[28:])
  		xlen := zget2(hdr[30:])
  		fclen := zget2(hdr[32:])
  		xattr := uint32(zget4(hdr[38:])) >> 16
  		off := zget4(hdr[42:])
  		name := hdr[46 : 46+namelen]
  		hdr = hdr[46+namelen+xlen+fclen:]
  
  		// zip per-file header layout:
  		//	0	magic[4]
  		//	4	extvers[1]
  		//	5	extos[1]
  		//	6	flags[2]
  		//	8	meth[2]
  		//	10	modtime[2]
  		//	12	moddate[2]
  		//	14	crc[4]
  		//	18	csize[4]
  		//	22	uncsize[4]
  		//	26	namelen[2]
  		//	28	xlen[2]
  		//	30	name[namelen]
  		//	30+namelen+xlen - file data
  		//
  		buf := data[off : off+zheadersize+namelen]
  		if zget4(buf) != zheader ||
  			zget2(buf[8:]) != meth ||
  			zget2(buf[26:]) != namelen ||
  			buf[30:30+namelen] != name {
  			println("fs unzip: inconsistent zip file")
  			return
  		}
  		xlen = zget2(buf[28:])
  
  		off += zheadersize + namelen + xlen
  
  		var fdata []byte
  		switch meth {
  		case 0:
  			// buf is uncompressed
  			buf = data[off : off+size]
  			fdata = []byte(buf)
  		case 8:
  			// buf is deflate-compressed
  			buf = data[off : off+csize]
  			fdata = inflate(buf)
  			if len(fdata) != size {
  				println("fs unzip: inconsistent size in zip file")
  				return
  			}
  		}
  
  		if xattr&S_IFMT == 0 {
  			if xattr&0777 == 0 {
  				xattr |= 0666
  			}
  			if len(name) > 0 && name[len(name)-1] == '/' {
  				xattr |= S_IFDIR
  				xattr |= 0111
  			} else {
  				xattr |= S_IFREG
  			}
  		}
  
  		if err := create(name, xattr, zipToTime(mdate, mtime), fdata); err != nil {
  			print("fs unzip: create ", name, ": ", err.Error(), "\n")
  		}
  	}
  
  	chdirEnv()
  }
  
  func zipToTime(date, time int) int64 {
  	dd := date & 0x1f
  	mm := date >> 5 & 0xf
  	yy := date >> 9 // since 1980
  
  	sec := int64(315532800) // jan 1 1980
  	sec += int64(yy) * 365 * 86400
  	sec += int64(yy) / 4 * 86400
  	if yy%4 > 0 || mm >= 3 {
  		sec += 86400
  	}
  	sec += int64(daysBeforeMonth[mm]) * 86400
  	sec += int64(dd-1) * 86400
  
  	h := time >> 11
  	m := time >> 5 & 0x3F
  	s := time & 0x1f * 2
  	sec += int64(h*3600 + m*60 + s)
  
  	return sec
  }
  
  var daysBeforeMonth = [...]int32{
  	0,
  	0,
  	31,
  	31 + 28,
  	31 + 28 + 31,
  	31 + 28 + 31 + 30,
  	31 + 28 + 31 + 30 + 31,
  	31 + 28 + 31 + 30 + 31 + 30,
  	31 + 28 + 31 + 30 + 31 + 30 + 31,
  	31 + 28 + 31 + 30 + 31 + 30 + 31 + 31,
  	31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30,
  	31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31,
  	31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 + 30,
  	31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 + 30 + 31,
  }
  

View as plain text