// 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,
}