1	/*
     2	Copyright 2013 The Perkeep Authors
     3	
     4	Licensed under the Apache License, Version 2.0 (the "License");
     5	you may not use this file except in compliance with the License.
     6	You may obtain a copy of the License at
     7	
     8	     http://www.apache.org/licenses/LICENSE-2.0
     9	
    10	Unless required by applicable law or agreed to in writing, software
    11	distributed under the License is distributed on an "AS IS" BASIS,
    12	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13	See the License for the specific language governing permissions and
    14	limitations under the License.
    15	*/
    16	
    17	// Package blob defines types to refer to and retrieve low-level Perkeep blobs.
    18	package blob // import "perkeep.org/pkg/blob"
    19	
    20	import (
    21		"bytes"
    22		"crypto/sha1"
    23		"crypto/sha256"
    24		"errors"
    25		"fmt"
    26		"hash"
    27		"io"
    28		"reflect"
    29		"strings"
    30	)
    31	
    32	// Pattern is the regular expression which matches a blobref.
    33	// It does not contain ^ or $.
    34	const Pattern = `\b([a-z][a-z0-9]*)-([a-f0-9]+)\b`
    35	
    36	// Ref is a reference to a Perkeep blob.
    37	// It is used as a value type and supports equality (with ==) and the ability
    38	// to use it as a map key.
    39	type Ref struct {
    40		digest digestType
    41	}
    42	
    43	// SizedRef is like a Ref but includes a size.
    44	// It should also be used as a value type and supports equality.
    45	type SizedRef struct {
    46		Ref  Ref    `json:"blobRef"`
    47		Size uint32 `json:"size"`
    48	}
    49	
    50	// Less reports whether sr sorts before o. Invalid references blobs sort first.
    51	func (sr SizedRef) Less(o SizedRef) bool {
    52		return sr.Ref.Less(o.Ref)
    53	}
    54	
    55	func (sr SizedRef) Valid() bool { return sr.Ref.Valid() }
    56	
    57	func (sr SizedRef) HashMatches(h hash.Hash) bool { return sr.Ref.HashMatches(h) }
    58	
    59	func (sr SizedRef) String() string {
    60		return fmt.Sprintf("[%s; %d bytes]", sr.Ref.String(), sr.Size)
    61	}
    62	
    63	// digestType is an interface type, but any type implementing it must
    64	// be of concrete type [N]byte, so it supports equality with ==,
    65	// which is a requirement for ref.
    66	type digestType interface {
    67		bytes() []byte
    68		digestName() string
    69		newHash() hash.Hash
    70		equalString(string) bool
    71		hasPrefix(string) bool
    72	}
    73	
    74	func (r Ref) String() string {
    75		if r.digest == nil {
    76			return "<invalid-blob.Ref>"
    77		}
    78		dname := r.digest.digestName()
    79		bs := r.digest.bytes()
    80		buf := getBuf(len(dname) + 1 + len(bs)*2)[:0]
    81		defer putBuf(buf)
    82		return string(r.appendString(buf))
    83	}
    84	
    85	// StringMinusOne returns the first string that's before String.
    86	func (r Ref) StringMinusOne() string {
    87		if r.digest == nil {
    88			return "<invalid-blob.Ref>"
    89		}
    90		dname := r.digest.digestName()
    91		bs := r.digest.bytes()
    92		buf := getBuf(len(dname) + 1 + len(bs)*2)[:0]
    93		defer putBuf(buf)
    94		buf = r.appendString(buf)
    95		buf[len(buf)-1]-- // no need to deal with carrying underflow (no 0 bytes ever)
    96		return string(buf)
    97	}
    98	
    99	// EqualString reports whether r.String() is equal to s.
   100	// It does not allocate.
   101	func (r Ref) EqualString(s string) bool { return r.digest.equalString(s) }
   102	
   103	// HasPrefix reports whether s is a prefix of r.String(). It returns false if s
   104	// does not contain at least the digest name prefix (e.g. "sha224-") and one byte of
   105	// digest.
   106	// It does not allocate.
   107	func (r Ref) HasPrefix(s string) bool { return r.digest.hasPrefix(s) }
   108	
   109	func (r Ref) appendString(buf []byte) []byte {
   110		dname := r.digest.digestName()
   111		bs := r.digest.bytes()
   112		buf = append(buf, dname...)
   113		buf = append(buf, '-')
   114		for _, b := range bs {
   115			buf = append(buf, hexDigit[b>>4], hexDigit[b&0xf])
   116		}
   117		if o, ok := r.digest.(otherDigest); ok && o.odd {
   118			buf = buf[:len(buf)-1]
   119		}
   120		return buf
   121	}
   122	
   123	// HashName returns the lowercase hash function name of the reference.
   124	// It panics if r is zero.
   125	func (r Ref) HashName() string {
   126		if r.digest == nil {
   127			panic("HashName called on invalid Ref")
   128		}
   129		return r.digest.digestName()
   130	}
   131	
   132	// Digest returns the lower hex digest of the blobref, without
   133	// the e.g. "sha224-" prefix. It panics if r is zero.
   134	func (r Ref) Digest() string {
   135		if r.digest == nil {
   136			panic("Digest called on invalid Ref")
   137		}
   138		bs := r.digest.bytes()
   139		buf := getBuf(len(bs) * 2)[:0]
   140		defer putBuf(buf)
   141		for _, b := range bs {
   142			buf = append(buf, hexDigit[b>>4], hexDigit[b&0xf])
   143		}
   144		if o, ok := r.digest.(otherDigest); ok && o.odd {
   145			buf = buf[:len(buf)-1]
   146		}
   147		return string(buf)
   148	}
   149	
   150	func (r Ref) DigestPrefix(digits int) string {
   151		v := r.Digest()
   152		if len(v) < digits {
   153			return v
   154		}
   155		return v[:digits]
   156	}
   157	
   158	func (r Ref) DomID() string {
   159		if !r.Valid() {
   160			return ""
   161		}
   162		return "camli-" + r.String()
   163	}
   164	
   165	func (r Ref) Sum32() uint32 {
   166		var v uint32
   167		for _, b := range r.digest.bytes()[:4] {
   168			v = v<<8 | uint32(b)
   169		}
   170		return v
   171	}
   172	
   173	func (r Ref) Sum64() uint64 {
   174		var v uint64
   175		for _, b := range r.digest.bytes()[:8] {
   176			v = v<<8 | uint64(b)
   177		}
   178		return v
   179	}
   180	
   181	// Hash returns a new hash.Hash of r's type.
   182	// It panics if r is zero.
   183	func (r Ref) Hash() hash.Hash {
   184		return r.digest.newHash()
   185	}
   186	
   187	func (r Ref) HashMatches(h hash.Hash) bool {
   188		if r.digest == nil {
   189			return false
   190		}
   191		return bytes.Equal(h.Sum(nil), r.digest.bytes())
   192	}
   193	
   194	const hexDigit = "0123456789abcdef"
   195	
   196	func (r Ref) Valid() bool { return r.digest != nil }
   197	
   198	func (r Ref) IsSupported() bool {
   199		if !r.Valid() {
   200			return false
   201		}
   202		_, ok := metaFromString[r.digest.digestName()]
   203		return ok
   204	}
   205	
   206	// ParseKnown is like Parse, but only parse blobrefs known to this
   207	// server. It returns ok == false for well-formed but unsupported
   208	// blobrefs.
   209	func ParseKnown(s string) (ref Ref, ok bool) {
   210		return parse(s, false)
   211	}
   212	
   213	// Parse parse s as a blobref and returns the ref and whether it was
   214	// parsed successfully.
   215	func Parse(s string) (ref Ref, ok bool) {
   216		return parse(s, true)
   217	}
   218	
   219	func parse(s string, allowAll bool) (ref Ref, ok bool) {
   220		i := strings.Index(s, "-")
   221		if i < 0 {
   222			return
   223		}
   224		name := s[:i] // e.g. "sha1", "sha224"
   225		hex := s[i+1:]
   226		meta, ok := metaFromString[name]
   227		if !ok {
   228			if allowAll || testRefType[name] {
   229				return parseUnknown(name, hex)
   230			}
   231			return
   232		}
   233		if len(hex) != meta.size*2 {
   234			ok = false
   235			return
   236		}
   237		dt, ok := meta.ctors(hex)
   238		if !ok {
   239			return
   240		}
   241		return Ref{dt}, true
   242	}
   243	
   244	var testRefType = map[string]bool{
   245		"fakeref": true,
   246		"testref": true,
   247		"perma":   true,
   248	}
   249	
   250	// ParseBytes is like Parse, but parses from a byte slice.
   251	func ParseBytes(s []byte) (ref Ref, ok bool) {
   252		i := bytes.IndexByte(s, '-')
   253		if i < 0 {
   254			return
   255		}
   256		name := s[:i] // e.g. "sha1", "sha224"
   257		hex := s[i+1:]
   258		meta, ok := metaFromBytes(name)
   259		if !ok {
   260			return parseUnknown(string(name), string(hex))
   261		}
   262		if len(hex) != meta.size*2 {
   263			ok = false
   264			return
   265		}
   266		dt, ok := meta.ctorb(hex)
   267		if !ok {
   268			return
   269		}
   270		return Ref{dt}, true
   271	}
   272	
   273	// ParseOrZero parses as a blobref. If s is invalid, a zero Ref is
   274	// returned which can be tested with the Valid method.
   275	func ParseOrZero(s string) Ref {
   276		ref, ok := Parse(s)
   277		if !ok {
   278			return Ref{}
   279		}
   280		return ref
   281	}
   282	
   283	// MustParse parse s as a blobref and panics on failure.
   284	func MustParse(s string) Ref {
   285		ref, ok := Parse(s)
   286		if !ok {
   287			panic("Invalid blobref " + s)
   288		}
   289		return ref
   290	}
   291	
   292	// '0' => 0 ... 'f' => 15, else sets *bad to true.
   293	func hexVal(b byte, bad *bool) byte {
   294		if '0' <= b && b <= '9' {
   295			return b - '0'
   296		}
   297		if 'a' <= b && b <= 'f' {
   298			return b - 'a' + 10
   299		}
   300		*bad = true
   301		return 0
   302	}
   303	
   304	func validDigestName(name string) bool {
   305		if name == "" {
   306			return false
   307		}
   308		for _, r := range name {
   309			if 'a' <= r && r <= 'z' {
   310				continue
   311			}
   312			if '0' <= r && r <= '9' {
   313				continue
   314			}
   315			return false
   316		}
   317		return true
   318	}
   319	
   320	// parseUnknown parses a blobref where the digest type isn't known to this server.
   321	// e.g. ("foo-ababab")
   322	func parseUnknown(digest, hex string) (ref Ref, ok bool) {
   323		if !validDigestName(digest) {
   324			return
   325		}
   326	
   327		// TODO: remove this short hack and don't allow odd numbers of hex digits.
   328		odd := false
   329		if len(hex)%2 != 0 {
   330			hex += "0"
   331			odd = true
   332		}
   333	
   334		if len(hex) < 2 || len(hex)%2 != 0 || len(hex) > maxOtherDigestLen*2 {
   335			return
   336		}
   337		o := otherDigest{
   338			name:   digest,
   339			sumLen: len(hex) / 2,
   340			odd:    odd,
   341		}
   342		bad := false
   343		for i := 0; i < len(hex); i += 2 {
   344			o.sum[i/2] = hexVal(hex[i], &bad)<<4 | hexVal(hex[i+1], &bad)
   345		}
   346		if bad {
   347			return
   348		}
   349		return Ref{o}, true
   350	}
   351	
   352	func sha1FromBinary(b []byte) digestType {
   353		var d sha1Digest
   354		if len(d) != len(b) {
   355			panic("bogus sha-1 length")
   356		}
   357		copy(d[:], b)
   358		return d
   359	}
   360	
   361	func sha1FromHexString(hex string) (digestType, bool) {
   362		var d sha1Digest
   363		var bad bool
   364		for i := 0; i < len(hex); i += 2 {
   365			d[i/2] = hexVal(hex[i], &bad)<<4 | hexVal(hex[i+1], &bad)
   366		}
   367		if bad {
   368			return nil, false
   369		}
   370		return d, true
   371	}
   372	
   373	// yawn. exact copy of sha1FromHexString.
   374	func sha1FromHexBytes(hex []byte) (digestType, bool) {
   375		var d sha1Digest
   376		var bad bool
   377		for i := 0; i < len(hex); i += 2 {
   378			d[i/2] = hexVal(hex[i], &bad)<<4 | hexVal(hex[i+1], &bad)
   379		}
   380		if bad {
   381			return nil, false
   382		}
   383		return d, true
   384	}
   385	
   386	func sha224FromBinary(b []byte) digestType {
   387		var d sha224Digest
   388		if len(d) != len(b) {
   389			panic("bogus sha-224 length")
   390		}
   391		copy(d[:], b)
   392		return d
   393	}
   394	
   395	func sha224FromHexString(hex string) (digestType, bool) {
   396		var d sha224Digest
   397		var bad bool
   398		for i := 0; i < len(hex); i += 2 {
   399			d[i/2] = hexVal(hex[i], &bad)<<4 | hexVal(hex[i+1], &bad)
   400		}
   401		if bad {
   402			return nil, false
   403		}
   404		return d, true
   405	}
   406	
   407	// yawn. exact copy of sha224FromHexString.
   408	func sha224FromHexBytes(hex []byte) (digestType, bool) {
   409		var d sha224Digest
   410		var bad bool
   411		for i := 0; i < len(hex); i += 2 {
   412			d[i/2] = hexVal(hex[i], &bad)<<4 | hexVal(hex[i+1], &bad)
   413		}
   414		if bad {
   415			return nil, false
   416		}
   417		return d, true
   418	}
   419	
   420	// RefFromHash returns a blobref representing the given hash.
   421	// It panics if the hash isn't of a known type.
   422	func RefFromHash(h hash.Hash) Ref {
   423		meta, ok := metaFromType[hashSig{reflect.TypeOf(h), h.Size()}]
   424		if !ok {
   425			panic(fmt.Sprintf("Currently-unsupported hash type %T", h))
   426		}
   427		return Ref{meta.ctor(h.Sum(nil))}
   428	}
   429	
   430	// RefFromString returns a blobref from the given string, for the currently
   431	// recommended hash function.
   432	func RefFromString(s string) Ref {
   433		h := NewHash()
   434		io.WriteString(h, s)
   435		return RefFromHash(h)
   436	}
   437	
   438	// RefFromBytes returns a blobref from the given string, for the currently
   439	// recommended hash function.
   440	func RefFromBytes(b []byte) Ref {
   441		h := NewHash()
   442		h.Write(b)
   443		return RefFromHash(h)
   444	}
   445	
   446	type sha1Digest [20]byte
   447	
   448	func (d sha1Digest) digestName() string { return "sha1" }
   449	func (d sha1Digest) bytes() []byte      { return d[:] }
   450	func (d sha1Digest) newHash() hash.Hash { return sha1.New() }
   451	func (d sha1Digest) equalString(s string) bool {
   452		if len(s) != 45 {
   453			return false
   454		}
   455		if !strings.HasPrefix(s, "sha1-") {
   456			return false
   457		}
   458		s = s[len("sha1-"):]
   459		for i, b := range d[:] {
   460			if s[i*2] != hexDigit[b>>4] || s[i*2+1] != hexDigit[b&0xf] {
   461				return false
   462			}
   463		}
   464		return true
   465	}
   466	
   467	func (d sha1Digest) hasPrefix(s string) bool {
   468		if len(s) > 45 {
   469			return false
   470		}
   471		if len(s) == 45 {
   472			return d.equalString(s)
   473		}
   474		if !strings.HasPrefix(s, "sha1-") {
   475			return false
   476		}
   477		s = s[len("sha1-"):]
   478		if len(s) == 0 {
   479			// we want at least one digest char to match on
   480			return false
   481		}
   482		for i, b := range d[:] {
   483			even := i * 2
   484			if even == len(s) {
   485				break
   486			}
   487			if s[even] != hexDigit[b>>4] {
   488				return false
   489			}
   490			odd := i*2 + 1
   491			if odd == len(s) {
   492				break
   493			}
   494			if s[odd] != hexDigit[b&0xf] {
   495				return false
   496			}
   497		}
   498		return true
   499	}
   500	
   501	type sha224Digest [28]byte
   502	
   503	const sha224StrLen = 63 // len("sha224-d14a028c2a3a2bc9476102bb288234c415a2b01f828ea62ac5b3e42f")
   504	
   505	func (d sha224Digest) digestName() string { return "sha224" }
   506	func (d sha224Digest) bytes() []byte      { return d[:] }
   507	func (d sha224Digest) newHash() hash.Hash { return sha256.New224() }
   508	func (d sha224Digest) equalString(s string) bool {
   509		if len(s) != sha224StrLen {
   510			return false
   511		}
   512		if !strings.HasPrefix(s, "sha224-") {
   513			return false
   514		}
   515		s = s[len("sha224-"):]
   516		for i, b := range d[:] {
   517			if s[i*2] != hexDigit[b>>4] || s[i*2+1] != hexDigit[b&0xf] {
   518				return false
   519			}
   520		}
   521		return true
   522	}
   523	
   524	func (d sha224Digest) hasPrefix(s string) bool {
   525		if len(s) > sha224StrLen {
   526			return false
   527		}
   528		if len(s) == sha224StrLen {
   529			return d.equalString(s)
   530		}
   531		if !strings.HasPrefix(s, "sha224-") {
   532			return false
   533		}
   534		s = s[len("sha224-"):]
   535		if len(s) == 0 {
   536			// we want at least one digest char to match on
   537			return false
   538		}
   539		for i, b := range d[:] {
   540			even := i * 2
   541			if even == len(s) {
   542				break
   543			}
   544			if s[even] != hexDigit[b>>4] {
   545				return false
   546			}
   547			odd := i*2 + 1
   548			if odd == len(s) {
   549				break
   550			}
   551			if s[odd] != hexDigit[b&0xf] {
   552				return false
   553			}
   554		}
   555		return true
   556	}
   557	
   558	const maxOtherDigestLen = 128
   559	
   560	type otherDigest struct {
   561		name   string
   562		sum    [maxOtherDigestLen]byte
   563		sumLen int  // bytes in sum that are valid
   564		odd    bool // odd number of hex digits in input
   565	}
   566	
   567	func (d otherDigest) digestName() string { return d.name }
   568	func (d otherDigest) bytes() []byte      { return d.sum[:d.sumLen] }
   569	func (d otherDigest) newHash() hash.Hash { return nil }
   570	func (d otherDigest) equalString(s string) bool {
   571		wantLen := len(d.name) + len("-") + 2*d.sumLen
   572		if d.odd {
   573			wantLen--
   574		}
   575		if len(s) != wantLen || !strings.HasPrefix(s, d.name) || s[len(d.name)] != '-' {
   576			return false
   577		}
   578		s = s[len(d.name)+1:]
   579		for i, b := range d.sum[:d.sumLen] {
   580			if s[i*2] != hexDigit[b>>4] {
   581				return false
   582			}
   583			if i == d.sumLen-1 && d.odd {
   584				break
   585			}
   586			if s[i*2+1] != hexDigit[b&0xf] {
   587				return false
   588			}
   589		}
   590		return true
   591	}
   592	
   593	func (d otherDigest) hasPrefix(s string) bool {
   594		maxLen := len(d.name) + len("-") + 2*d.sumLen
   595		if d.odd {
   596			maxLen--
   597		}
   598		if len(s) > maxLen || !strings.HasPrefix(s, d.name) || s[len(d.name)] != '-' {
   599			return false
   600		}
   601		if len(s) == maxLen {
   602			return d.equalString(s)
   603		}
   604		s = s[len(d.name)+1:]
   605		if len(s) == 0 {
   606			// we want at least one digest char to match on
   607			return false
   608		}
   609		for i, b := range d.sum[:d.sumLen] {
   610			even := i * 2
   611			if even == len(s) {
   612				break
   613			}
   614			if s[even] != hexDigit[b>>4] {
   615				return false
   616			}
   617			odd := i*2 + 1
   618			if odd == len(s) {
   619				break
   620			}
   621			if i == d.sumLen-1 && d.odd {
   622				break
   623			}
   624			if s[odd] != hexDigit[b&0xf] {
   625				return false
   626			}
   627		}
   628		return true
   629	}
   630	
   631	var (
   632		sha1Meta = &digestMeta{
   633			ctor:  sha1FromBinary,
   634			ctors: sha1FromHexString,
   635			ctorb: sha1FromHexBytes,
   636			size:  sha1.Size,
   637		}
   638		sha224Meta = &digestMeta{
   639			ctor:  sha224FromBinary,
   640			ctors: sha224FromHexString,
   641			ctorb: sha224FromHexBytes,
   642			size:  sha256.Size224,
   643		}
   644	)
   645	
   646	var metaFromString = map[string]*digestMeta{
   647		"sha1":   sha1Meta,
   648		"sha224": sha224Meta,
   649	}
   650	
   651	type blobTypeAndMeta struct {
   652		name []byte
   653		meta *digestMeta
   654	}
   655	
   656	var metas []blobTypeAndMeta
   657	
   658	func metaFromBytes(name []byte) (meta *digestMeta, ok bool) {
   659		for _, bm := range metas {
   660			if bytes.Equal(name, bm.name) {
   661				return bm.meta, true
   662			}
   663		}
   664		return
   665	}
   666	
   667	func init() {
   668		for name, meta := range metaFromString {
   669			metas = append(metas, blobTypeAndMeta{
   670				name: []byte(name),
   671				meta: meta,
   672			})
   673		}
   674	}
   675	
   676	// HashFuncs returns the names of the supported hash functions.
   677	func HashFuncs() []string {
   678		hashes := make([]string, len(metas))
   679		for i, m := range metas {
   680			hashes[i] = string(m.name)
   681		}
   682		return hashes
   683	}
   684	
   685	var (
   686		sha1Type   = reflect.TypeOf(sha1.New())
   687		sha224Type = reflect.TypeOf(sha256.New224())
   688	)
   689	
   690	// hashSig is the tuple (reflect.Type, hash size), for use as a map key.
   691	// The size disambiguates SHA-256 vs SHA-224, both of which have the same
   692	// reflect.Type (crypto/sha256.digest, but one has is224 bool set true).
   693	type hashSig struct {
   694		rt   reflect.Type
   695		size int
   696	}
   697	
   698	var metaFromType = map[hashSig]*digestMeta{
   699		{sha1Type, sha1.Size}:        sha1Meta,
   700		{sha224Type, sha256.Size224}: sha224Meta,
   701	}
   702	
   703	type digestMeta struct {
   704		ctor  func(binary []byte) digestType
   705		ctors func(hex string) (digestType, bool)
   706		ctorb func(hex []byte) (digestType, bool)
   707		size  int // bytes of digest
   708	}
   709	
   710	var bufPool = make(chan []byte, 20)
   711	
   712	func getBuf(size int) []byte {
   713		for {
   714			select {
   715			case b := <-bufPool:
   716				if cap(b) >= size {
   717					return b[:size]
   718				}
   719			default:
   720				return make([]byte, size)
   721			}
   722		}
   723	}
   724	
   725	func putBuf(b []byte) {
   726		select {
   727		case bufPool <- b:
   728		default:
   729		}
   730	}
   731	
   732	// NewHash returns a new hash.Hash of the currently recommended hash type.
   733	// Currently this is SHA-224, but is subject to change over time.
   734	func NewHash() hash.Hash {
   735		return sha256.New224()
   736	}
   737	
   738	func ValidRefString(s string) bool {
   739		// TODO: optimize to not allocate
   740		return ParseOrZero(s).Valid()
   741	}
   742	
   743	var null = []byte(`null`)
   744	
   745	func (r *Ref) UnmarshalJSON(d []byte) error {
   746		if r.digest != nil {
   747			return errors.New("Can't UnmarshalJSON into a non-zero Ref")
   748		}
   749		if len(d) == 0 || bytes.Equal(d, null) {
   750			return nil
   751		}
   752		if len(d) < 2 || d[0] != '"' || d[len(d)-1] != '"' {
   753			return fmt.Errorf("blob: expecting a JSON string to unmarshal, got %q", d)
   754		}
   755		d = d[1 : len(d)-1]
   756		p, ok := ParseBytes(d)
   757		if !ok {
   758			return fmt.Errorf("blobref: invalid blobref %q (%d)", d, len(d))
   759		}
   760		*r = p
   761		return nil
   762	}
   763	
   764	func (r Ref) MarshalJSON() ([]byte, error) {
   765		if !r.Valid() {
   766			return null, nil
   767		}
   768		dname := r.digest.digestName()
   769		bs := r.digest.bytes()
   770		buf := make([]byte, 0, 3+len(dname)+len(bs)*2)
   771		buf = append(buf, '"')
   772		buf = r.appendString(buf)
   773		buf = append(buf, '"')
   774		return buf, nil
   775	}
   776	
   777	// MarshalBinary implements Go's encoding.BinaryMarshaler interface.
   778	func (r Ref) MarshalBinary() (data []byte, err error) {
   779		dname := r.digest.digestName()
   780		bs := r.digest.bytes()
   781		data = make([]byte, 0, len(dname)+1+len(bs))
   782		data = append(data, dname...)
   783		data = append(data, '-')
   784		data = append(data, bs...)
   785		return
   786	}
   787	
   788	// UnmarshalBinary implements Go's encoding.BinaryUnmarshaler interface.
   789	func (r *Ref) UnmarshalBinary(data []byte) error {
   790		if r.digest != nil {
   791			return errors.New("Can't UnmarshalBinary into a non-zero Ref")
   792		}
   793		i := bytes.IndexByte(data, '-')
   794		if i < 1 {
   795			return errors.New("no digest name")
   796		}
   797	
   798		digName := string(data[:i])
   799		buf := data[i+1:]
   800	
   801		meta, ok := metaFromString[digName]
   802		if !ok {
   803			r2, ok := parseUnknown(digName, fmt.Sprintf("%x", buf))
   804			if !ok {
   805				return errors.New("invalid blobref binary data")
   806			}
   807			*r = r2
   808			return nil
   809		}
   810		if len(buf) != meta.size {
   811			return errors.New("wrong size of data for digest " + digName)
   812		}
   813		r.digest = meta.ctor(buf)
   814		return nil
   815	}
   816	
   817	// Less reports whether r sorts before o. Invalid references blobs sort first.
   818	func (r Ref) Less(o Ref) bool {
   819		if r.Valid() != o.Valid() {
   820			return o.Valid()
   821		}
   822		if !r.Valid() {
   823			return false
   824		}
   825		if n1, n2 := r.digest.digestName(), o.digest.digestName(); n1 != n2 {
   826			return n1 < n2
   827		}
   828		return bytes.Compare(r.digest.bytes(), o.digest.bytes()) < 0
   829	}
   830	
   831	// ByRef sorts blob references.
   832	type ByRef []Ref
   833	
   834	func (s ByRef) Len() int           { return len(s) }
   835	func (s ByRef) Less(i, j int) bool { return s[i].Less(s[j]) }
   836	func (s ByRef) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
   837	
   838	// SizedByRef sorts SizedRefs by their blobref.
   839	type SizedByRef []SizedRef
   840	
   841	func (s SizedByRef) Len() int           { return len(s) }
   842	func (s SizedByRef) Less(i, j int) bool { return s[i].Less(s[j]) }
   843	func (s SizedByRef) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
   844	
   845	// TypeAlphabet returns the valid characters in the given blobref type.
   846	// It returns the empty string if the typ is unknown.
   847	func TypeAlphabet(typ string) string {
   848		switch typ {
   849		case "sha1":
   850			return hexDigit
   851		case "sha224":
   852			return hexDigit
   853		}
   854		return ""
   855	}