1package rsync
  2
  3import (
  4	"bytes"
  5	"hash"
  6)
  7
  8// matcher finds the receiver's blocks in the file being sent and emits the
  9// delta (rsync's match.c).
 10type matcher struct {
 11	head      sumHead
 12	sums      []sumBuf
 13	cs        *checksums
 14	tok       tokenSender
 15	buf       *mapFile
 16	sum       hash.Hash
 17	lastMatch int64
 18	inplace   bool // the receiver updates its basis file in place
 19
 20	tablesize uint32
 21	table     []int32
 22
 23	literal int64
 24	matched int64
 25}
 26
 27// matched sends the literal data before offset and, for i >= 0, the token of
 28// block i. i == -1 ends the file and i == -2 only flushes literal data.
 29func (m *matcher) emit(offset int64, i int32) error {
 30	n := offset - m.lastMatch
 31	var block []byte
 32	if i >= 0 {
 33		block = m.buf.ptr(offset, int(m.sums[i].len))
 34		// Copy, the literal ptr below may move the window.
 35		block = append([]byte(nil), block...)
 36	}
 37	literal := m.buf.ptr(m.lastMatch, int(n))
 38	if err := m.tok.send(i, literal, block); err != nil {
 39		return err
 40	}
 41	m.literal += n
 42	total := n
 43	if i >= 0 {
 44		m.matched += int64(m.sums[i].len)
 45		total += int64(m.sums[i].len)
 46	}
 47	for j := int64(0); j < total; j += chunkSize {
 48		n1 := min(chunkSize, total-j)
 49		m.sum.Write(m.buf.ptr(m.lastMatch+j, int(n1)))
 50	}
 51	if i >= 0 {
 52		m.lastMatch = offset + int64(m.sums[i].len)
 53	} else {
 54		m.lastMatch = offset
 55	}
 56	return nil
 57}
 58
 59func (m *matcher) buildTable() {
 60	m.tablesize = uint32(m.head.count/8)*10 + 11
 61	if m.tablesize < traditionalTableSize {
 62		m.tablesize = traditionalTableSize
 63	}
 64	m.table = make([]int32, m.tablesize)
 65	for i := range m.table {
 66		m.table[i] = -1
 67	}
 68	for i := range m.sums {
 69		var t uint32
 70		if m.tablesize == traditionalTableSize {
 71			s := m.sums[i].sum1
 72			t = (s&0xFFFF + s>>16) & 0xFFFF
 73		} else {
 74			t = m.sums[i].sum1 % m.tablesize
 75		}
 76		m.sums[i].chain = m.table[t]
 77		m.table[t] = int32(i)
 78	}
 79}
 80
 81// run sends a file of length size.
 82func (m *matcher) run(size int64) error {
 83	if size > 0 && m.head.count > 0 {
 84		m.buildTable()
 85		if err := m.hashSearch(size); err != nil {
 86			return err
 87		}
 88	} else {
 89		for j := m.lastMatch + chunkSize; j < size; j += chunkSize {
 90			if err := m.emit(j, -2); err != nil {
 91				return err
 92			}
 93		}
 94		if err := m.emit(size, -1); err != nil {
 95			return err
 96		}
 97	}
 98	return nil
 99}
100
101func (m *matcher) hashSearch(size int64) error {
102	var sum2 []byte
103	wantI := int32(0)
104	blength := int64(m.head.blength)
105	k := min(size, blength)
106	sum := checksum1(m.buf.ptr(0, int(k)))
107	s1, s2 := sum&0xFFFF, sum>>16
108	var offset, alignedOffset int64
109	alignedI := int32(0)
110	end := size + 1 - int64(m.sums[len(m.sums)-1].len)
111	s2len := int(m.head.s2length)
112
113	for {
114		doneCsum2 := false
115		var hashEntry uint32
116		if m.tablesize == traditionalTableSize {
117			hashEntry = (s1 + s2) & 0xFFFF
118			sum = s1&0xffff | s2<<16
119		} else {
120			sum = s1&0xffff | s2<<16
121			hashEntry = sum % m.tablesize
122		}
123		i := m.table[hashEntry]
124		prev := &m.table[hashEntry]
125		chainLen := 0
126		for ; i >= 0; i = m.sums[i].chain {
127			// An in-place receiver can only use blocks at or after the
128			// current offset, or ones it has left untouched.
129			if m.inplace && m.sums[i].offset < offset && !m.sums[i].same {
130				*prev = m.sums[i].chain
131				continue
132			}
133			prev = &m.sums[i].chain
134			if sum != m.sums[i].sum1 {
135				continue
136			}
137			chainLen++
138			if chainLen > maxChainLen {
139				break
140			}
141			l := int32(min(blength, size-offset))
142			if l != m.sums[i].len {
143				continue
144			}
145			if !doneCsum2 {
146				sum2 = m.cs.blockSum(m.buf.ptr(offset, int(l)), sum2[:0])
147				doneCsum2 = true
148			}
149			if !bytes.Equal(sum2[:s2len], m.sums[i].sum2) {
150				continue
151			}
152
153			if m.inplace {
154				for alignedOffset < offset {
155					alignedOffset += blength
156					alignedI++
157				}
158				if (offset == alignedOffset || (sum == 0 && int64(l) == blength && alignedOffset+int64(l) <= size)) && alignedI < m.head.count {
159					ok := true
160					if i != alignedI {
161						a := &m.sums[alignedI]
162						if sum != a.sum1 || l != a.len || !bytes.Equal(sum2[:s2len], a.sum2) {
163							ok = false
164						} else {
165							i = alignedI
166						}
167					}
168					if ok && offset != alignedOffset {
169						backup := max(alignedOffset-m.lastMatch, 0)
170						block := m.buf.ptr(alignedOffset-backup, int(int64(l)+backup))[backup:]
171						if checksum1(block) != m.sums[i].sum1 ||
172							!bytes.Equal(m.cs.blockSum(block, nil)[:s2len], m.sums[i].sum2) {
173							ok = false
174						} else {
175							offset = alignedOffset
176						}
177					}
178					if ok {
179						m.sums[i].same = true
180						wantI = i
181					}
182				}
183			}
184
185			if i != wantI && wantI < m.head.count &&
186				(!m.inplace || m.sums[wantI].offset >= offset || m.sums[wantI].same) &&
187				sum == m.sums[wantI].sum1 && l == m.sums[wantI].len &&
188				bytes.Equal(sum2[:s2len], m.sums[wantI].sum2) {
189				// Prefer the adjacent block so the token runs compress.
190				i = wantI
191			}
192			wantI = i + 1
193
194			if err := m.emit(offset, i); err != nil {
195				return err
196			}
197			offset += int64(m.sums[i].len) - 1
198			k = min(blength, size-offset)
199			sum = checksum1(m.buf.ptr(offset, int(k)))
200			s1, s2 = sum&0xFFFF, sum>>16
201			break
202		}
203
204		backup := max(offset-m.lastMatch, 0)
205		more := offset+k < size
206		n := k + backup
207		if more {
208			n++
209		}
210		window := m.buf.ptr(offset-backup, int(n))[backup:]
211		first := uint32(int8(window[0]))
212		s1 -= first
213		s2 -= uint32(k) * first
214		if more {
215			s1 += uint32(int8(window[k]))
216			s2 += s1
217		} else {
218			k--
219		}
220
221		if backup >= blength+chunkSize && end-offset > chunkSize {
222			if err := m.emit(offset-blength, -2); err != nil {
223				return err
224			}
225		}
226
227		offset++
228		if offset >= end {
229			break
230		}
231	}
232	return m.emit(size, -1)
233}