src/mth.go

   1 /*
   2 NNCP -- Node to Node copy, utilities for store-and-forward data exchange
   3 Copyright (C) 2016-2021 Sergey Matveev <stargrave@stargrave.org>
   4
   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.
   8
   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.
  13
  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/>.
  16 */
  17
  18 package nncp
  19
  20 import (
  21         "bytes"
  22         "encoding/hex"
  23         "errors"
  24         "fmt"
  25         "hash"
  26         "io"
  27
  28         "lukechampine.com/blake3"
  29 )
  30
  31 const (
  32         MTHBlockSize = 128 * 1024
  33         MTHSize      = 32
  34 )
  35
  36 var (
  37         MTHLeafKey = blake3.Sum256([]byte("NNCP MTH LEAF"))
  38         MTHNodeKey = blake3.Sum256([]byte("NNCP MTH NODE"))
  39 )
  40
  41 type MTHSeqEnt struct {
  42         l int
  43         c int64
  44         h [MTHSize]byte
  45 }
  46
  47 func (ent *MTHSeqEnt) String() string {
  48         return fmt.Sprintf("%03d\t%06d\t%s", ent.l, ent.c, hex.EncodeToString(ent.h[:]))
  49 }
  50
  51 type MTHEventType string
  52
  53 const (
  54         MTHEventAdd    MTHEventType = "Add"
  55         MTHEventPreadd MTHEventType = "Pre"
  56         MTHEventFold   MTHEventType = "Fold"
  57 )
  58
  59 type MTHEvent struct {
  60         Type MTHEventType
  61         Ent  *MTHSeqEnt
  62 }
  63
  64 func (e MTHEvent) String() string {
  65         return fmt.Sprintf("%s\t%s", e.Type, e.Ent.String())
  66 }
  67
  68 type MTH interface {
  69         hash.Hash
  70         PreaddFrom(r io.Reader, pktName string, showPrgrs bool) (int64, error)
  71         PreaddSize() int64
  72         Events() chan MTHEvent
  73 }
  74
  75 type MTHSeq struct {
  76         hasherLeaf  *blake3.Hasher
  77         hasherNode  *blake3.Hasher
  78         hashes      []MTHSeqEnt
  79         buf         *bytes.Buffer
  80         events      chan MTHEvent
  81         ctr         int64
  82         size        int64
  83         prependSize int64
  84         toSkip      int64
  85         skipped     bool
  86         finished    bool
  87         pktName     string
  88 }
  89
  90 func MTHSeqNew(size, offset int64) *MTHSeq {
  91         mth := MTHSeq{
  92                 hasherLeaf: blake3.New(MTHSize, MTHLeafKey[:]),
  93                 hasherNode: blake3.New(MTHSize, MTHNodeKey[:]),
  94                 buf:        bytes.NewBuffer(make([]byte, 0, 2*MTHBlockSize)),
  95         }
  96         if size == 0 {
  97                 return &mth
  98         }
  99         prepends := offset / MTHBlockSize
 100         toSkip := MTHBlockSize - (offset - prepends*MTHBlockSize)
 101         if toSkip == MTHBlockSize {
 102                 toSkip = 0
 103         } else if toSkip > 0 {
 104                 prepends++
 105         }
 106         prependSize := prepends * MTHBlockSize
 107         mth.ctr = prepends
 108         if prependSize > size {
 109                 prependSize = size
 110         }
 111         if offset+toSkip > size {
 112                 toSkip = size - offset
 113         }
 114         mth.size = size
 115         mth.prependSize = prependSize
 116         mth.toSkip = toSkip
 117         return &mth
 118 }
 119
 120 func (mth *MTHSeq) Reset() { panic("not implemented") }
 121
 122 func (mth *MTHSeq) Size() int { return MTHSize }
 123
 124 func (mth *MTHSeq) BlockSize() int { return MTHBlockSize }
 125
 126 func (mth *MTHSeq) PreaddFrom(r io.Reader, pktName string, showPrgrs bool) (int64, error) {
 127         if mth.finished {
 128                 return 0, errors.New("already Sum()ed")
 129         }
 130         if mth.buf.Len() > 0 {
 131                 if _, err := mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
 132                         panic(err)
 133                 }
 134                 mth.leafAdd()
 135                 mth.fold()
 136         }
 137         prevHashes := mth.hashes
 138         mth.hashes = nil
 139         prevCtr := mth.ctr
 140         mth.ctr = 0
 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)
 146                 mth.fold()
 147         }
 148         if mth.buf.Len() > 0 {
 149                 mth.ctr = prevCtr - 1
 150         } else {
 151                 mth.ctr = prevCtr
 152         }
 153         return n, err
 154 }
 155
 156 func (mth *MTHSeq) Events() chan MTHEvent {
 157         mth.events = make(chan MTHEvent)
 158         return mth.events
 159 }
 160
 161 func (mth *MTHSeq) PreaddSize() int64 { return mth.prependSize }
 162
 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)
 168         mth.ctr++
 169         if mth.events != nil {
 170                 mth.events <- MTHEvent{MTHEventAdd, &ent}
 171         }
 172 }
 173
 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]
 179                 if end1.c%2 == 1 {
 180                         break
 181                 }
 182                 if end1.l != end0.l {
 183                         break
 184                 }
 185                 if _, err := mth.hasherNode.Write(end1.h[:]); err != nil {
 186                         panic(err)
 187                 }
 188                 if _, err := mth.hasherNode.Write(end0.h[:]); err != nil {
 189                         panic(err)
 190                 }
 191                 mth.hashes = mth.hashes[:hlen-1]
 192                 end1.l++
 193                 end1.c /= 2
 194                 mth.hasherNode.Sum(end1.h[:0])
 195                 mth.hasherNode.Reset()
 196                 if mth.events != nil {
 197                         mth.events <- MTHEvent{MTHEventFold, end1}
 198                 }
 199         }
 200 }
 201
 202 func (mth *MTHSeq) Write(data []byte) (int, error) {
 203         if mth.finished {
 204                 return 0, errors.New("already Sum()ed")
 205         }
 206         n, err := mth.buf.Write(data)
 207         if err != nil {
 208                 return n, err
 209         }
 210         if mth.toSkip > 0 {
 211                 if int64(mth.buf.Len()) < mth.toSkip {
 212                         return n, err
 213                 }
 214                 mth.buf.Next(int(mth.toSkip))
 215                 mth.toSkip = 0
 216         }
 217         for mth.buf.Len() >= MTHBlockSize {
 218                 if _, err = mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
 219                         return n, err
 220                 }
 221                 mth.leafAdd()
 222                 mth.fold()
 223         }
 224         return n, err
 225 }
 226
 227 func (mth *MTHSeq) Sum(b []byte) []byte {
 228         if mth.finished {
 229                 return append(b, mth.hashes[0].h[:]...)
 230         }
 231         if mth.buf.Len() > 0 {
 232                 if _, err := mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
 233                         panic(err)
 234                 }
 235                 mth.leafAdd()
 236                 mth.fold()
 237         }
 238         switch mth.ctr {
 239         case 0:
 240                 if _, err := mth.hasherLeaf.Write(nil); err != nil {
 241                         panic(err)
 242                 }
 243                 mth.leafAdd()
 244                 fallthrough
 245         case 1:
 246                 ent := MTHSeqEnt{c: 1}
 247                 copy(ent.h[:], mth.hashes[0].h[:])
 248                 mth.ctr = 2
 249                 mth.hashes = append(mth.hashes, ent)
 250                 if mth.events != nil {
 251                         mth.events <- MTHEvent{MTHEventAdd, &ent}
 252                 }
 253                 mth.fold()
 254         }
 255         for len(mth.hashes) >= 2 {
 256                 hlen := len(mth.hashes)
 257                 end1 := &mth.hashes[hlen-2]
 258                 end0 := &mth.hashes[hlen-1]
 259                 end0.l = end1.l
 260                 end0.c = end1.c + 1
 261                 if mth.events != nil {
 262                         mth.events <- MTHEvent{MTHEventAdd, end0}
 263                 }
 264                 mth.fold()
 265         }
 266         mth.finished = true
 267         if mth.events != nil {
 268                 close(mth.events)
 269         }
 270         return append(b, mth.hashes[0].h[:]...)
 271 }
 272
 273 func MTHNew(size, offset int64) MTH {
 274         return MTHSeqNew(size, offset)
 275 }
 276
 277 // Some kind of reference implementation (fat, because eats memory)
 278
 279 type MTHFat struct {
 280         hasher *blake3.Hasher
 281         hashes [][MTHSize]byte
 282         buf    *bytes.Buffer
 283         events chan MTHEvent
 284 }
 285
 286 func MTHFatNew() *MTHFat {
 287         return &MTHFat{
 288                 hasher: blake3.New(MTHSize, MTHLeafKey[:]),
 289                 buf:    bytes.NewBuffer(make([]byte, 0, 2*MTHBlockSize)),
 290         }
 291 }
 292
 293 func (mth *MTHFat) Events() chan MTHEvent {
 294         mth.events = make(chan MTHEvent)
 295         return mth.events
 296 }
 297
 298 func (mth *MTHFat) Write(data []byte) (int, error) {
 299         n, err := mth.buf.Write(data)
 300         if err != nil {
 301                 return n, err
 302         }
 303         for mth.buf.Len() >= MTHBlockSize {
 304                 if _, err = mth.hasher.Write(mth.buf.Next(MTHBlockSize)); err != nil {
 305                         return n, err
 306                 }
 307                 h := new([MTHSize]byte)
 308                 mth.hasher.Sum(h[:0])
 309                 mth.hasher.Reset()
 310                 mth.hashes = append(mth.hashes, *h)
 311                 if mth.events != nil {
 312                         mth.events <- MTHEvent{
 313                                 MTHEventAdd,
 314                                 &MTHSeqEnt{
 315                                         0, int64(len(mth.hashes) - 1),
 316                                         mth.hashes[len(mth.hashes)-1],
 317                                 },
 318                         }
 319                 }
 320         }
 321         return n, err
 322 }
 323
 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 {
 328                         panic(err)
 329                 }
 330                 h := new([MTHSize]byte)
 331                 mth.hasher.Sum(h[:0])
 332                 mth.hasher.Reset()
 333                 mth.hashes = append(mth.hashes, *h)
 334                 if mth.events != nil {
 335                         mth.events <- MTHEvent{
 336                                 MTHEventAdd,
 337                                 &MTHSeqEnt{
 338                                         0, int64(len(mth.hashes) - 1),
 339                                         mth.hashes[len(mth.hashes)-1],
 340                                 },
 341                         }
 342                 }
 343         }
 344         switch len(mth.hashes) {
 345         case 0:
 346                 h := new([MTHSize]byte)
 347                 if _, err := mth.hasher.Write(nil); err != nil {
 348                         panic(err)
 349                 }
 350                 mth.hasher.Sum(h[:0])
 351                 mth.hasher.Reset()
 352                 mth.hashes = append(mth.hashes, *h)
 353                 if mth.events != nil {
 354                         mth.events <- MTHEvent{MTHEventAdd, &MTHSeqEnt{0, 0, mth.hashes[0]}}
 355                 }
 356                 fallthrough
 357         case 1:
 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]}}
 361                 }
 362         }
 363         mth.hasher = blake3.New(MTHSize, MTHNodeKey[:])
 364         level := 1
 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 {
 370                                 panic(err)
 371                         }
 372                         if _, err := mth.hasher.Write(mth.hashes[i+1][:]); err != nil {
 373                                 panic(err)
 374                         }
 375                         h := new([MTHSize]byte)
 376                         mth.hasher.Sum(h[:0])
 377                         mth.hasher.Reset()
 378                         hashesUp = append(hashesUp, *h)
 379                         if mth.events != nil {
 380                                 mth.events <- MTHEvent{
 381                                         MTHEventFold,
 382                                         &MTHSeqEnt{
 383                                                 level, int64(len(hashesUp) - 1),
 384                                                 hashesUp[len(hashesUp)-1],
 385                                         },
 386                                 }
 387                         }
 388                 }
 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{
 393                                         MTHEventAdd,
 394                                         &MTHSeqEnt{
 395                                                 level, int64(len(hashesUp) - 1),
 396                                                 hashesUp[len(hashesUp)-1],
 397                                         },
 398                                 }
 399                         }
 400                 }
 401                 mth.hashes = hashesUp
 402                 level++
 403         }
 404         if mth.events != nil {
 405                 close(mth.events)
 406         }
 407         return append(b, mth.hashes[0][:]...)
 408 }