2 NNCP -- Node to Node copy, utilities for store-and-forward data exchange
3 Copyright (C) 2016-2022 Sergey Matveev <stargrave@stargrave.org>
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, version 3 of the License.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>.
28 "lukechampine.com/blake3"
32 MTHBlockSize = 128 * 1024
37 MTHLeafKey = blake3.Sum256([]byte("NNCP MTH LEAF"))
38 MTHNodeKey = blake3.Sum256([]byte("NNCP MTH NODE"))
41 type MTHSeqEnt struct {
47 func (ent *MTHSeqEnt) String() string {
48 return fmt.Sprintf("%03d\t%06d\t%s", ent.l, ent.c, hex.EncodeToString(ent.h[:]))
51 type MTHEventType string
54 MTHEventAdd MTHEventType = "Add"
55 MTHEventPreadd MTHEventType = "Pre"
56 MTHEventFold MTHEventType = "Fold"
59 type MTHEvent struct {
64 func (e MTHEvent) String() string {
65 return fmt.Sprintf("%s\t%s", e.Type, e.Ent.String())
70 PreaddFrom(r io.Reader, pktName string, showPrgrs bool) (int64, error)
72 Events() chan MTHEvent
76 hasherLeaf *blake3.Hasher
77 hasherNode *blake3.Hasher
90 func MTHSeqNew(size, offset int64) *MTHSeq {
92 hasherLeaf: blake3.New(MTHSize, MTHLeafKey[:]),
93 hasherNode: blake3.New(MTHSize, MTHNodeKey[:]),
94 buf: bytes.NewBuffer(make([]byte, 0, 2*MTHBlockSize)),
99 prepends := offset / MTHBlockSize
100 toSkip := MTHBlockSize - (offset - prepends*MTHBlockSize)
101 if toSkip == MTHBlockSize {
103 } else if toSkip > 0 {
106 prependSize := prepends * MTHBlockSize
108 if prependSize > size {
111 if offset+toSkip > size {
112 toSkip = size - offset
115 mth.prependSize = prependSize
120 func (mth *MTHSeq) Reset() { panic("not implemented") }
122 func (mth *MTHSeq) Size() int { return MTHSize }
124 func (mth *MTHSeq) BlockSize() int { return MTHBlockSize }
126 func (mth *MTHSeq) PreaddFrom(r io.Reader, pktName string, showPrgrs bool) (int64, error) {
128 return 0, errors.New("already Sum()ed")
130 if mth.buf.Len() > 0 {
131 if _, err := mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
137 prevHashes := mth.hashes
141 lr := io.LimitedReader{R: r, N: mth.prependSize}
142 les := LEs{{"Pkt", pktName}, {"FullSize", mth.prependSize}}
143 n, err := CopyProgressed(mth, &lr, "prehash", les, showPrgrs)
144 for _, ent := range prevHashes {
145 mth.hashes = append(mth.hashes, ent)
148 if mth.buf.Len() > 0 {
149 mth.ctr = prevCtr - 1
156 func (mth *MTHSeq) Events() chan MTHEvent {
157 mth.events = make(chan MTHEvent)
161 func (mth *MTHSeq) PreaddSize() int64 { return mth.prependSize }
163 func (mth *MTHSeq) leafAdd() {
164 ent := MTHSeqEnt{c: mth.ctr}
165 mth.hasherLeaf.Sum(ent.h[:0])
166 mth.hasherLeaf.Reset()
167 mth.hashes = append(mth.hashes, ent)
169 if mth.events != nil {
170 mth.events <- MTHEvent{MTHEventAdd, &ent}
174 func (mth *MTHSeq) fold() {
175 for len(mth.hashes) >= 2 {
176 hlen := len(mth.hashes)
177 end1 := &mth.hashes[hlen-2]
178 end0 := &mth.hashes[hlen-1]
182 if end1.l != end0.l {
185 if _, err := mth.hasherNode.Write(end1.h[:]); err != nil {
188 if _, err := mth.hasherNode.Write(end0.h[:]); err != nil {
191 mth.hashes = mth.hashes[:hlen-1]
194 mth.hasherNode.Sum(end1.h[:0])
195 mth.hasherNode.Reset()
196 if mth.events != nil {
197 mth.events <- MTHEvent{MTHEventFold, end1}
202 func (mth *MTHSeq) Write(data []byte) (int, error) {
204 return 0, errors.New("already Sum()ed")
206 n, err := mth.buf.Write(data)
211 if int64(mth.buf.Len()) < mth.toSkip {
214 mth.buf.Next(int(mth.toSkip))
217 for mth.buf.Len() >= MTHBlockSize {
218 if _, err = mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
227 func (mth *MTHSeq) Sum(b []byte) []byte {
229 return append(b, mth.hashes[0].h[:]...)
231 if mth.buf.Len() > 0 {
232 if _, err := mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
240 if _, err := mth.hasherLeaf.Write(nil); err != nil {
246 ent := MTHSeqEnt{c: 1}
247 copy(ent.h[:], mth.hashes[0].h[:])
249 mth.hashes = append(mth.hashes, ent)
250 if mth.events != nil {
251 mth.events <- MTHEvent{MTHEventAdd, &ent}
255 for len(mth.hashes) >= 2 {
256 hlen := len(mth.hashes)
257 end1 := &mth.hashes[hlen-2]
258 end0 := &mth.hashes[hlen-1]
261 if mth.events != nil {
262 mth.events <- MTHEvent{MTHEventAdd, end0}
267 if mth.events != nil {
270 return append(b, mth.hashes[0].h[:]...)
273 func MTHNew(size, offset int64) MTH {
274 return MTHSeqNew(size, offset)
277 // Some kind of reference implementation (fat, because eats memory)
280 hasher *blake3.Hasher
281 hashes [][MTHSize]byte
286 func MTHFatNew() *MTHFat {
288 hasher: blake3.New(MTHSize, MTHLeafKey[:]),
289 buf: bytes.NewBuffer(make([]byte, 0, 2*MTHBlockSize)),
293 func (mth *MTHFat) Events() chan MTHEvent {
294 mth.events = make(chan MTHEvent)
298 func (mth *MTHFat) Write(data []byte) (int, error) {
299 n, err := mth.buf.Write(data)
303 for mth.buf.Len() >= MTHBlockSize {
304 if _, err = mth.hasher.Write(mth.buf.Next(MTHBlockSize)); err != nil {
307 h := new([MTHSize]byte)
308 mth.hasher.Sum(h[:0])
310 mth.hashes = append(mth.hashes, *h)
311 if mth.events != nil {
312 mth.events <- MTHEvent{
315 0, int64(len(mth.hashes) - 1),
316 mth.hashes[len(mth.hashes)-1],
324 func (mth *MTHFat) Sum(b []byte) []byte {
325 if mth.buf.Len() > 0 {
326 b := mth.buf.Next(MTHBlockSize)
327 if _, err := mth.hasher.Write(b); err != nil {
330 h := new([MTHSize]byte)
331 mth.hasher.Sum(h[:0])
333 mth.hashes = append(mth.hashes, *h)
334 if mth.events != nil {
335 mth.events <- MTHEvent{
338 0, int64(len(mth.hashes) - 1),
339 mth.hashes[len(mth.hashes)-1],
344 switch len(mth.hashes) {
346 h := new([MTHSize]byte)
347 if _, err := mth.hasher.Write(nil); err != nil {
350 mth.hasher.Sum(h[:0])
352 mth.hashes = append(mth.hashes, *h)
353 if mth.events != nil {
354 mth.events <- MTHEvent{MTHEventAdd, &MTHSeqEnt{0, 0, mth.hashes[0]}}
358 mth.hashes = append(mth.hashes, mth.hashes[0])
359 if mth.events != nil {
360 mth.events <- MTHEvent{MTHEventAdd, &MTHSeqEnt{0, 1, mth.hashes[1]}}
363 mth.hasher = blake3.New(MTHSize, MTHNodeKey[:])
365 for len(mth.hashes) != 1 {
366 hashesUp := make([][MTHSize]byte, 0, 1+len(mth.hashes)/2)
367 pairs := (len(mth.hashes) / 2) * 2
368 for i := 0; i < pairs; i += 2 {
369 if _, err := mth.hasher.Write(mth.hashes[i][:]); err != nil {
372 if _, err := mth.hasher.Write(mth.hashes[i+1][:]); err != nil {
375 h := new([MTHSize]byte)
376 mth.hasher.Sum(h[:0])
378 hashesUp = append(hashesUp, *h)
379 if mth.events != nil {
380 mth.events <- MTHEvent{
383 level, int64(len(hashesUp) - 1),
384 hashesUp[len(hashesUp)-1],
389 if len(mth.hashes)%2 == 1 {
390 hashesUp = append(hashesUp, mth.hashes[len(mth.hashes)-1])
391 if mth.events != nil {
392 mth.events <- MTHEvent{
395 level, int64(len(hashesUp) - 1),
396 hashesUp[len(hashesUp)-1],
401 mth.hashes = hashesUp
404 if mth.events != nil {
407 return append(b, mth.hashes[0][:]...)