1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Package git85 implements the radix 85 data encoding
6 // used in the Git version control system.
16 type CorruptInputError int64
18 func (e CorruptInputError) String() string {
19 return "illegal git85 data at input byte " + strconv.Itoa64(int64(e))
22 const encode = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~"
24 // The decodings are 1+ the actual value, so that the
25 // default zero value can be used to mean "not valid".
26 var decode = [256]uint8{
27 '0': 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
28 'A': 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
29 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,
30 'a': 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
31 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62,
43 // Encode encodes src into EncodedLen(len(src))
44 // bytes of dst. As a convenience, it returns the number
45 // of bytes written to dst, but this value is always EncodedLen(len(src)).
46 // Encode implements the radix 85 encoding used in the
47 // Git version control tool.
49 // The encoding splits src into chunks of at most 52 bytes
50 // and encodes each chunk on its own line.
51 func Encode(dst, src []byte) int {
59 dst[ndst] = byte('A' + n - 1)
61 dst[ndst] = byte('a' + n - 26 - 1)
64 for i := 0; i < n; i += 4 {
66 for j := 0; j < 4 && i+j < n; j++ {
67 v |= uint32(src[i+j]) << uint(24-j*8)
69 for j := 4; j >= 0; j-- {
70 dst[ndst+j] = encode[v%85]
82 // EncodedLen returns the length of an encoding of n source bytes.
83 func EncodedLen(n int) int {
87 // 5 bytes per 4 bytes of input, rounded up.
88 // 2 extra bytes for each line of 52 src bytes, rounded up.
89 return (n+3)/4*5 + (n+51)/52*2
92 var newline = []byte{'\n'}
94 // Decode decodes src into at most MaxDecodedLen(len(src))
95 // bytes, returning the actual number of bytes written to dst.
97 // If Decode encounters invalid input, it returns a CorruptInputError.
99 func Decode(dst, src []byte) (n int, err os.Error) {
102 for nsrc < len(src) {
104 switch ch := int(src[nsrc]); {
105 case 'A' <= ch && ch <= 'Z':
107 case 'a' <= ch && ch <= 'z':
108 l = ch - 'a' + 26 + 1
110 return ndst, CorruptInputError(nsrc)
112 if nsrc+1+l > len(src) {
113 return ndst, CorruptInputError(nsrc)
115 el := (l + 3) / 4 * 5 // encoded len
116 if nsrc+1+el+1 > len(src) || src[nsrc+1+el] != '\n' {
117 return ndst, CorruptInputError(nsrc)
119 line := src[nsrc+1 : nsrc+1+el]
120 for i := 0; i < el; i += 5 {
122 for j := 0; j < 5; j++ {
123 ch := decode[line[i+j]]
125 return ndst, CorruptInputError(nsrc + 1 + i + j)
127 v = v*85 + uint32(ch-1)
129 for j := 0; j < 4; j++ {
130 dst[ndst] = byte(v >> 24)
135 // Last fragment may have run too far (but there was room in dst).
145 func MaxDecodedLen(n int) int { return n / 5 * 4 }
147 // NewEncoder returns a new Git base85 stream encoder. Data written to
148 // the returned writer will be encoded and then written to w.
149 // The Git encoding operates on 52-byte blocks; when finished
150 // writing, the caller must Close the returned encoder to flush any
151 // partially written blocks.
152 func NewEncoder(w io.Writer) io.WriteCloser { return &encoder{w: w} }
154 type encoder struct {
163 func (e *encoder) Write(p []byte) (n int, err os.Error) {
171 for i = 0; i < len(p) && e.nbuf < 52; i++ {
180 nout := Encode(e.out[0:], e.buf[0:])
181 if _, e.err = e.w.Write(e.out[0:nout]); e.err != nil {
187 // Large interior chunks.
189 nn := len(e.out) / (1 + 52/4*5 + 1) * 52
191 nn = len(p) / 52 * 52
194 nout := Encode(e.out[0:], p[0:nn])
195 if _, e.err = e.w.Write(e.out[0:nout]); e.err != nil {
204 for i := 0; i < len(p); i++ {
212 func (e *encoder) Close() os.Error {
213 // If there's anything left in the buffer, flush it out
214 if e.err == nil && e.nbuf > 0 {
215 nout := Encode(e.out[0:], e.buf[0:e.nbuf])
217 _, e.err = e.w.Write(e.out[0:nout])
222 // NewDecoder returns a new Git base85 stream decoder.
223 func NewDecoder(r io.Reader) io.Reader { return &decoder{r: r} }
225 type decoder struct {
236 func (d *decoder) Read(p []byte) (n int, err os.Error) {
242 // Copy leftover output from last decode.
249 // Out of decoded output. Check errors.
253 if d.readErr != nil {
258 // Read and decode more input.
260 nn, d.readErr = d.r.Read(d.buf[d.nbuf:])
263 // Send complete lines to Decode.
264 nl := bytes.LastIndex(d.buf[0:d.nbuf], newline)
268 nn, d.err = Decode(d.outbuf[0:], d.buf[0:nl+1])
269 if e, ok := d.err.(CorruptInputError); ok {
270 d.err = CorruptInputError(int64(e) + d.off)
272 d.out = d.outbuf[0:nn]
273 d.nbuf = copy(d.buf[0:], d.buf[nl+1:d.nbuf])
274 d.off += int64(nl + 1)
276 panic("unreacahable")