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.
4
5// Package hex implements hexadecimal encoding and decoding.
6package hex
7
8import (
9	"errors"
10	"fmt"
11	"io"
12	"slices"
13	"strings"
14)
15
16const (
17	hextable        = "0123456789abcdef"
18	reverseHexTable = "" +
19		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
20		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
21		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
22		"\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\xff\xff\xff\xff\xff\xff" +
23		"\xff\x0a\x0b\x0c\x0d\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
24		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
25		"\xff\x0a\x0b\x0c\x0d\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
26		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
27		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
28		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
29		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
30		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
31		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
32		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
33		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
34		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
35)
36
37// EncodedLen returns the length of an encoding of n source bytes.
38// Specifically, it returns n * 2.
39func EncodedLen(n int) int { return n * 2 }
40
41// Encode encodes src into [EncodedLen](len(src))
42// bytes of dst. As a convenience, it returns the number
43// of bytes written to dst, but this value is always [EncodedLen](len(src)).
44// Encode implements hexadecimal encoding.
45func Encode(dst, src []byte) int {
46	j := 0
47	for _, v := range src {
48		dst[j] = hextable[v>>4]
49		dst[j+1] = hextable[v&0x0f]
50		j += 2
51	}
52	return len(src) * 2
53}
54
55// AppendEncode appends the hexadecimally encoded src to dst
56// and returns the extended buffer.
57func AppendEncode(dst, src []byte) []byte {
58	n := EncodedLen(len(src))
59	dst = slices.Grow(dst, n)
60	Encode(dst[len(dst):][:n], src)
61	return dst[:len(dst)+n]
62}
63
64// ErrLength reports an attempt to decode an odd-length input
65// using [Decode] or [DecodeString].
66// The stream-based Decoder returns [io.ErrUnexpectedEOF] instead of ErrLength.
67var ErrLength = errors.New("encoding/hex: odd length hex string")
68
69// InvalidByteError values describe errors resulting from an invalid byte in a hex string.
70type InvalidByteError byte
71
72func (e InvalidByteError) Error() string {
73	return fmt.Sprintf("encoding/hex: invalid byte: %#U", rune(e))
74}
75
76// DecodedLen returns the length of a decoding of x source bytes.
77// Specifically, it returns x / 2.
78func DecodedLen(x int) int { return x / 2 }
79
80// Decode decodes src into [DecodedLen](len(src)) bytes,
81// returning the actual number of bytes written to dst.
82//
83// Decode expects that src contains only hexadecimal
84// characters and that src has even length.
85// If the input is malformed, Decode returns the number
86// of bytes decoded before the error.
87func Decode(dst, src []byte) (int, error) {
88	i, j := 0, 1
89	for ; j < len(src); j += 2 {
90		p := src[j-1]
91		q := src[j]
92
93		a := reverseHexTable[p]
94		b := reverseHexTable[q]
95		if a > 0x0f {
96			return i, InvalidByteError(p)
97		}
98		if b > 0x0f {
99			return i, InvalidByteError(q)
100		}
101		dst[i] = (a << 4) | b
102		i++
103	}
104	if len(src)%2 == 1 {
105		// Check for invalid char before reporting bad length,
106		// since the invalid char (if present) is an earlier problem.
107		if reverseHexTable[src[j-1]] > 0x0f {
108			return i, InvalidByteError(src[j-1])
109		}
110		return i, ErrLength
111	}
112	return i, nil
113}
114
115// AppendDecode appends the hexadecimally decoded src to dst
116// and returns the extended buffer.
117// If the input is malformed, it returns the partially decoded src and an error.
118func AppendDecode(dst, src []byte) ([]byte, error) {
119	n := DecodedLen(len(src))
120	dst = slices.Grow(dst, n)
121	n, err := Decode(dst[len(dst):][:n], src)
122	return dst[:len(dst)+n], err
123}
124
125// EncodeToString returns the hexadecimal encoding of src.
126func EncodeToString(src []byte) string {
127	dst := make([]byte, EncodedLen(len(src)))
128	Encode(dst, src)
129	return string(dst)
130}
131
132// DecodeString returns the bytes represented by the hexadecimal string s.
133//
134// DecodeString expects that src contains only hexadecimal
135// characters and that src has even length.
136// If the input is malformed, DecodeString returns
137// the bytes decoded before the error.
138func DecodeString(s string) ([]byte, error) {
139	dst := make([]byte, DecodedLen(len(s)))
140	n, err := Decode(dst, []byte(s))
141	return dst[:n], err
142}
143
144// Dump returns a string that contains a hex dump of the given data. The format
145// of the hex dump matches the output of `hexdump -C` on the command line.
146func Dump(data []byte) string {
147	if len(data) == 0 {
148		return ""
149	}
150
151	var buf strings.Builder
152	// Dumper will write 79 bytes per complete 16 byte chunk, and at least
153	// 64 bytes for whatever remains. Round the allocation up, since only a
154	// maximum of 15 bytes will be wasted.
155	buf.Grow((1 + ((len(data) - 1) / 16)) * 79)
156
157	dumper := Dumper(&buf)
158	dumper.Write(data)
159	dumper.Close()
160	return buf.String()
161}
162
163// bufferSize is the number of hexadecimal characters to buffer in encoder and decoder.
164const bufferSize = 1024
165
166type encoder struct {
167	w   io.Writer
168	err error
169	out [bufferSize]byte // output buffer
170}
171
172// NewEncoder returns an [io.Writer] that writes lowercase hexadecimal characters to w.
173func NewEncoder(w io.Writer) io.Writer {
174	return &encoder{w: w}
175}
176
177func (e *encoder) Write(p []byte) (n int, err error) {
178	for len(p) > 0 && e.err == nil {
179		chunkSize := bufferSize / 2
180		if len(p) < chunkSize {
181			chunkSize = len(p)
182		}
183
184		var written int
185		encoded := Encode(e.out[:], p[:chunkSize])
186		written, e.err = e.w.Write(e.out[:encoded])
187		n += written / 2
188		p = p[chunkSize:]
189	}
190	return n, e.err
191}
192
193type decoder struct {
194	r   io.Reader
195	err error
196	in  []byte           // input buffer (encoded form)
197	arr [bufferSize]byte // backing array for in
198}
199
200// NewDecoder returns an [io.Reader] that decodes hexadecimal characters from r.
201// NewDecoder expects that r contain only an even number of hexadecimal characters.
202func NewDecoder(r io.Reader) io.Reader {
203	return &decoder{r: r}
204}
205
206func (d *decoder) Read(p []byte) (n int, err error) {
207	// Fill internal buffer with sufficient bytes to decode
208	if len(d.in) < 2 && d.err == nil {
209		var numCopy, numRead int
210		numCopy = copy(d.arr[:], d.in) // Copies either 0 or 1 bytes
211		numRead, d.err = d.r.Read(d.arr[numCopy:])
212		d.in = d.arr[:numCopy+numRead]
213		if d.err == io.EOF && len(d.in)%2 != 0 {
214
215			if a := reverseHexTable[d.in[len(d.in)-1]]; a > 0x0f {
216				d.err = InvalidByteError(d.in[len(d.in)-1])
217			} else {
218				d.err = io.ErrUnexpectedEOF
219			}
220		}
221	}
222
223	// Decode internal buffer into output buffer
224	if numAvail := len(d.in) / 2; len(p) > numAvail {
225		p = p[:numAvail]
226	}
227	numDec, err := Decode(p, d.in[:len(p)*2])
228	d.in = d.in[2*numDec:]
229	if err != nil {
230		d.in, d.err = nil, err // Decode error; discard input remainder
231	}
232
233	if len(d.in) < 2 {
234		return numDec, d.err // Only expose errors when buffer fully consumed
235	}
236	return numDec, nil
237}
238
239// Dumper returns a [io.WriteCloser] that writes a hex dump of all written data to
240// w. The format of the dump matches the output of `hexdump -C` on the command
241// line.
242func Dumper(w io.Writer) io.WriteCloser {
243	return &dumper{w: w}
244}
245
246type dumper struct {
247	w          io.Writer
248	rightChars [18]byte
249	buf        [14]byte
250	used       int  // number of bytes in the current line
251	n          uint // number of bytes, total
252	closed     bool
253}
254
255func toChar(b byte) byte {
256	if b < 32 || b > 126 {
257		return '.'
258	}
259	return b
260}
261
262func (h *dumper) Write(data []byte) (n int, err error) {
263	if h.closed {
264		return 0, errors.New("encoding/hex: dumper closed")
265	}
266
267	// Output lines look like:
268	// 00000010  2e 2f 30 31 32 33 34 35  36 37 38 39 3a 3b 3c 3d  |./0123456789:;<=|
269	// ^ offset                          ^ extra space              ^ ASCII of line.
270	for i := range data {
271		if h.used == 0 {
272			// At the beginning of a line we print the current
273			// offset in hex.
274			h.buf[0] = byte(h.n >> 24)
275			h.buf[1] = byte(h.n >> 16)
276			h.buf[2] = byte(h.n >> 8)
277			h.buf[3] = byte(h.n)
278			Encode(h.buf[4:], h.buf[:4])
279			h.buf[12] = ' '
280			h.buf[13] = ' '
281			_, err = h.w.Write(h.buf[4:])
282			if err != nil {
283				return
284			}
285		}
286		Encode(h.buf[:], data[i:i+1])
287		h.buf[2] = ' '
288		l := 3
289		if h.used == 7 {
290			// There's an additional space after the 8th byte.
291			h.buf[3] = ' '
292			l = 4
293		} else if h.used == 15 {
294			// At the end of the line there's an extra space and
295			// the bar for the right column.
296			h.buf[3] = ' '
297			h.buf[4] = '|'
298			l = 5
299		}
300		_, err = h.w.Write(h.buf[:l])
301		if err != nil {
302			return
303		}
304		n++
305		h.rightChars[h.used] = toChar(data[i])
306		h.used++
307		h.n++
308		if h.used == 16 {
309			h.rightChars[16] = '|'
310			h.rightChars[17] = '\n'
311			_, err = h.w.Write(h.rightChars[:])
312			if err != nil {
313				return
314			}
315			h.used = 0
316		}
317	}
318	return
319}
320
321func (h *dumper) Close() (err error) {
322	// See the comments in Write() for the details of this format.
323	if h.closed {
324		return
325	}
326	h.closed = true
327	if h.used == 0 {
328		return
329	}
330	h.buf[0] = ' '
331	h.buf[1] = ' '
332	h.buf[2] = ' '
333	h.buf[3] = ' '
334	h.buf[4] = '|'
335	nBytes := h.used
336	for h.used < 16 {
337		l := 3
338		if h.used == 7 {
339			l = 4
340		} else if h.used == 15 {
341			l = 5
342		}
343		_, err = h.w.Write(h.buf[:l])
344		if err != nil {
345			return
346		}
347		h.used++
348	}
349	h.rightChars[nBytes] = '|'
350	h.rightChars[nBytes+1] = '\n'
351	_, err = h.w.Write(h.rightChars[:nBytes+2])
352	return
353}
354