src/mth.go

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