X-Git-Url: http://www.git.cypherpunks.ru/?a=blobdiff_plain;f=src%2Fmth.go;h=ff39237f4a6fa1c64a9f07477417b412f919a039;hb=0367cce2741e1ce6a89a49fd5c4e9df6005c9744;hp=6cb1f3640b6f180fa363f6b8c9b7664f4ff0787a;hpb=1cc0df98a8d949b9f8137081b875d98a1aae2e67;p=nncp.git

diff --git a/src/mth.go b/src/mth.go
index 6cb1f36..ff39237 100644
--- a/src/mth.go
+++ b/src/mth.go
@@ -1,6 +1,6 @@
 /*
 NNCP -- Node to Node copy, utilities for store-and-forward data exchange
-Copyright (C) 2016-2021 Sergey Matveev <stargrave@stargrave.org>
+Copyright (C) 2016-2022 Sergey Matveev <stargrave@stargrave.org>
 
 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
@@ -19,7 +19,10 @@ package nncp
 
 import (
 	"bytes"
+	"encoding/hex"
 	"errors"
+	"fmt"
+	"hash"
 	"io"
 
 	"lukechampine.com/blake3"
@@ -35,70 +38,168 @@ var (
 	MTHNodeKey = blake3.Sum256([]byte("NNCP MTH NODE"))
 )
 
-type MTHEventType uint8
+type MTHSeqEnt struct {
+	l int
+	c int64
+	h [MTHSize]byte
+}
+
+func (ent *MTHSeqEnt) String() string {
+	return fmt.Sprintf("%03d\t%06d\t%s", ent.l, ent.c, hex.EncodeToString(ent.h[:]))
+}
+
+type MTHEventType string
 
 const (
-	MTHEventAppend  MTHEventType = iota
-	MTHEventPrepend MTHEventType = iota
-	MTHEventFold    MTHEventType = iota
+	MTHEventAdd    MTHEventType = "Add"
+	MTHEventPreadd MTHEventType = "Pre"
+	MTHEventFold   MTHEventType = "Fold"
 )
 
 type MTHEvent struct {
-	Type  MTHEventType
-	Level int
-	Ctr   int
-	Hsh   []byte
+	Type MTHEventType
+	Ent  *MTHSeqEnt
+}
+
+func (e MTHEvent) String() string {
+	return fmt.Sprintf("%s\t%s", e.Type, e.Ent.String())
 }
 
-type MTH struct {
+type MTH interface {
+	hash.Hash
+	PreaddFrom(r io.Reader, pktName string, showPrgrs bool) (int64, error)
+	PreaddSize() int64
+	Events() chan MTHEvent
+}
+
+type MTHSeq struct {
+	hasherLeaf  *blake3.Hasher
+	hasherNode  *blake3.Hasher
+	hashes      []MTHSeqEnt
+	buf         *bytes.Buffer
+	events      chan MTHEvent
+	ctr         int64
 	size        int64
-	PrependSize int64
-	skip        int64
+	prependSize int64
+	toSkip      int64
 	skipped     bool
-	hasher      *blake3.Hasher
-	hashes      [][MTHSize]byte
-	buf         *bytes.Buffer
 	finished    bool
-	Events      chan MTHEvent
-	PktName     string
+	pktName     string
 }
 
-func MTHNew(size, offset int64) *MTH {
-	mth := MTH{
-		hasher: blake3.New(MTHSize, MTHLeafKey[:]),
-		buf:    bytes.NewBuffer(make([]byte, 0, 2*MTHBlockSize)),
+func MTHSeqNew(size, offset int64) *MTHSeq {
+	mth := MTHSeq{
+		hasherLeaf: blake3.New(MTHSize, MTHLeafKey[:]),
+		hasherNode: blake3.New(MTHSize, MTHNodeKey[:]),
+		buf:        bytes.NewBuffer(make([]byte, 0, 2*MTHBlockSize)),
 	}
 	if size == 0 {
 		return &mth
 	}
-	prepends := int(offset / MTHBlockSize)
-	skip := MTHBlockSize - (offset - int64(prepends)*MTHBlockSize)
-	if skip == MTHBlockSize {
-		skip = 0
-	} else if skip > 0 {
+	prepends := offset / MTHBlockSize
+	toSkip := MTHBlockSize - (offset - prepends*MTHBlockSize)
+	if toSkip == MTHBlockSize {
+		toSkip = 0
+	} else if toSkip > 0 {
 		prepends++
 	}
-	prependSize := int64(prepends * MTHBlockSize)
+	prependSize := prepends * MTHBlockSize
+	mth.ctr = prepends
 	if prependSize > size {
 		prependSize = size
 	}
-	if offset+skip > size {
-		skip = size - offset
+	if offset+toSkip > size {
+		toSkip = size - offset
 	}
 	mth.size = size
-	mth.PrependSize = prependSize
-	mth.skip = skip
-	mth.hashes = make([][MTHSize]byte, prepends, 1+size/MTHBlockSize)
+	mth.prependSize = prependSize
+	mth.toSkip = toSkip
 	return &mth
 }
 
-func (mth *MTH) Reset() { panic("not implemented") }
+func (mth *MTHSeq) Reset() { panic("not implemented") }
 
-func (mth *MTH) Size() int { return MTHSize }
+func (mth *MTHSeq) Size() int { return MTHSize }
 
-func (mth *MTH) BlockSize() int { return MTHBlockSize }
+func (mth *MTHSeq) BlockSize() int { return MTHBlockSize }
 
-func (mth *MTH) Write(data []byte) (int, error) {
+func (mth *MTHSeq) PreaddFrom(r io.Reader, pktName string, showPrgrs bool) (int64, error) {
+	if mth.finished {
+		return 0, errors.New("already Sum()ed")
+	}
+	if mth.buf.Len() > 0 {
+		if _, err := mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
+			panic(err)
+		}
+		mth.leafAdd()
+		mth.fold()
+	}
+	prevHashes := mth.hashes
+	mth.hashes = nil
+	prevCtr := mth.ctr
+	mth.ctr = 0
+	lr := io.LimitedReader{R: r, N: mth.prependSize}
+	les := LEs{{"Pkt", pktName}, {"FullSize", mth.prependSize}}
+	n, err := CopyProgressed(mth, &lr, "prehash", les, showPrgrs)
+	for _, ent := range prevHashes {
+		mth.hashes = append(mth.hashes, ent)
+		mth.fold()
+	}
+	if mth.buf.Len() > 0 {
+		mth.ctr = prevCtr - 1
+	} else {
+		mth.ctr = prevCtr
+	}
+	return n, err
+}
+
+func (mth *MTHSeq) Events() chan MTHEvent {
+	mth.events = make(chan MTHEvent)
+	return mth.events
+}
+
+func (mth *MTHSeq) PreaddSize() int64 { return mth.prependSize }
+
+func (mth *MTHSeq) leafAdd() {
+	ent := MTHSeqEnt{c: mth.ctr}
+	mth.hasherLeaf.Sum(ent.h[:0])
+	mth.hasherLeaf.Reset()
+	mth.hashes = append(mth.hashes, ent)
+	mth.ctr++
+	if mth.events != nil {
+		mth.events <- MTHEvent{MTHEventAdd, &ent}
+	}
+}
+
+func (mth *MTHSeq) fold() {
+	for len(mth.hashes) >= 2 {
+		hlen := len(mth.hashes)
+		end1 := &mth.hashes[hlen-2]
+		end0 := &mth.hashes[hlen-1]
+		if end1.c%2 == 1 {
+			break
+		}
+		if end1.l != end0.l {
+			break
+		}
+		if _, err := mth.hasherNode.Write(end1.h[:]); err != nil {
+			panic(err)
+		}
+		if _, err := mth.hasherNode.Write(end0.h[:]); err != nil {
+			panic(err)
+		}
+		mth.hashes = mth.hashes[:hlen-1]
+		end1.l++
+		end1.c /= 2
+		mth.hasherNode.Sum(end1.h[:0])
+		mth.hasherNode.Reset()
+		if mth.events != nil {
+			mth.events <- MTHEvent{MTHEventFold, end1}
+		}
+	}
+}
+
+func (mth *MTHSeq) Write(data []byte) (int, error) {
 	if mth.finished {
 		return 0, errors.New("already Sum()ed")
 	}
@@ -106,85 +207,121 @@ func (mth *MTH) Write(data []byte) (int, error) {
 	if err != nil {
 		return n, err
 	}
-	if mth.skip > 0 && int64(mth.buf.Len()) >= mth.skip {
-		mth.buf.Next(int(mth.skip))
-		mth.skip = 0
+	if mth.toSkip > 0 {
+		if int64(mth.buf.Len()) < mth.toSkip {
+			return n, err
+		}
+		mth.buf.Next(int(mth.toSkip))
+		mth.toSkip = 0
 	}
 	for mth.buf.Len() >= MTHBlockSize {
-		if _, err = mth.hasher.Write(mth.buf.Next(MTHBlockSize)); err != nil {
+		if _, err = mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
 			return n, err
 		}
-		h := new([MTHSize]byte)
-		mth.hasher.Sum(h[:0])
-		mth.hasher.Reset()
-		mth.hashes = append(mth.hashes, *h)
-		if mth.Events != nil {
-			mth.Events <- MTHEvent{
-				MTHEventAppend,
-				0, len(mth.hashes) - 1,
-				mth.hashes[len(mth.hashes)-1][:],
-			}
-		}
+		mth.leafAdd()
+		mth.fold()
 	}
 	return n, err
 }
 
-func (mth *MTH) PrependFrom(r io.Reader) (int, error) {
+func (mth *MTHSeq) Sum(b []byte) []byte {
 	if mth.finished {
-		return 0, errors.New("already Sum()ed")
+		return append(b, mth.hashes[0].h[:]...)
 	}
-	var err error
-	buf := make([]byte, MTHBlockSize)
-	var i, n, read int
-	fullsize := mth.PrependSize
-	les := LEs{{"Pkt", mth.PktName}, {"FullSize", fullsize}, {"Size", 0}}
-	for mth.PrependSize >= MTHBlockSize {
-		n, err = io.ReadFull(r, buf)
-		read += n
-		mth.PrependSize -= MTHBlockSize
-		if err != nil {
-			return read, err
-		}
-		if _, err = mth.hasher.Write(buf); err != nil {
+	if mth.buf.Len() > 0 {
+		if _, err := mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
 			panic(err)
 		}
-		mth.hasher.Sum(mth.hashes[i][:0])
-		mth.hasher.Reset()
-		if mth.Events != nil {
-			mth.Events <- MTHEvent{MTHEventPrepend, 0, i, mth.hashes[i][:]}
+		mth.leafAdd()
+		mth.fold()
+	}
+	switch mth.ctr {
+	case 0:
+		if _, err := mth.hasherLeaf.Write(nil); err != nil {
+			panic(err)
 		}
-		if mth.PktName != "" {
-			les[len(les)-1].V = int64(read)
-			Progress("check", les)
+		mth.leafAdd()
+		fallthrough
+	case 1:
+		ent := MTHSeqEnt{c: 1}
+		copy(ent.h[:], mth.hashes[0].h[:])
+		mth.ctr = 2
+		mth.hashes = append(mth.hashes, ent)
+		if mth.events != nil {
+			mth.events <- MTHEvent{MTHEventAdd, &ent}
 		}
-		i++
+		mth.fold()
 	}
-	if mth.PrependSize > 0 {
-		n, err = io.ReadFull(r, buf[:mth.PrependSize])
-		read += n
-		if err != nil {
-			return read, err
+	for len(mth.hashes) >= 2 {
+		hlen := len(mth.hashes)
+		end1 := &mth.hashes[hlen-2]
+		end0 := &mth.hashes[hlen-1]
+		end0.l = end1.l
+		end0.c = end1.c + 1
+		if mth.events != nil {
+			mth.events <- MTHEvent{MTHEventAdd, end0}
 		}
-		if _, err = mth.hasher.Write(buf[:mth.PrependSize]); err != nil {
-			panic(err)
+		mth.fold()
+	}
+	mth.finished = true
+	if mth.events != nil {
+		close(mth.events)
+	}
+	return append(b, mth.hashes[0].h[:]...)
+}
+
+func MTHNew(size, offset int64) MTH {
+	return MTHSeqNew(size, offset)
+}
+
+// Some kind of reference implementation (fat, because eats memory)
+
+type MTHFat struct {
+	hasher *blake3.Hasher
+	hashes [][MTHSize]byte
+	buf    *bytes.Buffer
+	events chan MTHEvent
+}
+
+func MTHFatNew() *MTHFat {
+	return &MTHFat{
+		hasher: blake3.New(MTHSize, MTHLeafKey[:]),
+		buf:    bytes.NewBuffer(make([]byte, 0, 2*MTHBlockSize)),
+	}
+}
+
+func (mth *MTHFat) Events() chan MTHEvent {
+	mth.events = make(chan MTHEvent)
+	return mth.events
+}
+
+func (mth *MTHFat) Write(data []byte) (int, error) {
+	n, err := mth.buf.Write(data)
+	if err != nil {
+		return n, err
+	}
+	for mth.buf.Len() >= MTHBlockSize {
+		if _, err = mth.hasher.Write(mth.buf.Next(MTHBlockSize)); err != nil {
+			return n, err
 		}
-		mth.hasher.Sum(mth.hashes[i][:0])
+		h := new([MTHSize]byte)
+		mth.hasher.Sum(h[:0])
 		mth.hasher.Reset()
-		if mth.Events != nil {
-			mth.Events <- MTHEvent{MTHEventPrepend, 0, i, mth.hashes[i][:]}
-		}
-		if mth.PktName != "" {
-			les[len(les)-1].V = fullsize
-			Progress("check", les)
+		mth.hashes = append(mth.hashes, *h)
+		if mth.events != nil {
+			mth.events <- MTHEvent{
+				MTHEventAdd,
+				&MTHSeqEnt{
+					0, int64(len(mth.hashes) - 1),
+					mth.hashes[len(mth.hashes)-1],
+				},
+			}
 		}
 	}
-	return read, nil
+	return n, err
 }
 
-func (mth *MTH) Sum(b []byte) []byte {
-	if mth.finished {
-		return append(b, mth.hashes[0][:]...)
-	}
+func (mth *MTHFat) Sum(b []byte) []byte {
 	if mth.buf.Len() > 0 {
 		b := mth.buf.Next(MTHBlockSize)
 		if _, err := mth.hasher.Write(b); err != nil {
@@ -194,11 +331,13 @@ func (mth *MTH) Sum(b []byte) []byte {
 		mth.hasher.Sum(h[:0])
 		mth.hasher.Reset()
 		mth.hashes = append(mth.hashes, *h)
-		if mth.Events != nil {
-			mth.Events <- MTHEvent{
-				MTHEventAppend,
-				0, len(mth.hashes) - 1,
-				mth.hashes[len(mth.hashes)-1][:],
+		if mth.events != nil {
+			mth.events <- MTHEvent{
+				MTHEventAdd,
+				&MTHSeqEnt{
+					0, int64(len(mth.hashes) - 1),
+					mth.hashes[len(mth.hashes)-1],
+				},
 			}
 		}
 	}
@@ -211,14 +350,14 @@ func (mth *MTH) Sum(b []byte) []byte {
 		mth.hasher.Sum(h[:0])
 		mth.hasher.Reset()
 		mth.hashes = append(mth.hashes, *h)
-		if mth.Events != nil {
-			mth.Events <- MTHEvent{MTHEventAppend, 0, 0, mth.hashes[0][:]}
+		if mth.events != nil {
+			mth.events <- MTHEvent{MTHEventAdd, &MTHSeqEnt{0, 0, mth.hashes[0]}}
 		}
 		fallthrough
 	case 1:
 		mth.hashes = append(mth.hashes, mth.hashes[0])
-		if mth.Events != nil {
-			mth.Events <- MTHEvent{MTHEventAppend, 0, 1, mth.hashes[1][:]}
+		if mth.events != nil {
+			mth.events <- MTHEvent{MTHEventAdd, &MTHSeqEnt{0, 1, mth.hashes[1]}}
 		}
 	}
 	mth.hasher = blake3.New(MTHSize, MTHNodeKey[:])
@@ -237,30 +376,33 @@ func (mth *MTH) Sum(b []byte) []byte {
 			mth.hasher.Sum(h[:0])
 			mth.hasher.Reset()
 			hashesUp = append(hashesUp, *h)
-			if mth.Events != nil {
-				mth.Events <- MTHEvent{
+			if mth.events != nil {
+				mth.events <- MTHEvent{
 					MTHEventFold,
-					level, len(hashesUp) - 1,
-					hashesUp[len(hashesUp)-1][:],
+					&MTHSeqEnt{
+						level, int64(len(hashesUp) - 1),
+						hashesUp[len(hashesUp)-1],
+					},
 				}
 			}
 		}
 		if len(mth.hashes)%2 == 1 {
 			hashesUp = append(hashesUp, mth.hashes[len(mth.hashes)-1])
-			if mth.Events != nil {
-				mth.Events <- MTHEvent{
-					MTHEventAppend,
-					level, len(hashesUp) - 1,
-					hashesUp[len(hashesUp)-1][:],
+			if mth.events != nil {
+				mth.events <- MTHEvent{
+					MTHEventAdd,
+					&MTHSeqEnt{
+						level, int64(len(hashesUp) - 1),
+						hashesUp[len(hashesUp)-1],
+					},
 				}
 			}
 		}
 		mth.hashes = hashesUp
 		level++
 	}
-	mth.finished = true
-	if mth.Events != nil {
-		close(mth.Events)
+	if mth.events != nil {
+		close(mth.events)
 	}
 	return append(b, mth.hashes[0][:]...)
 }