src/mth.go

   1 /*
   2 NNCP -- Node to Node copy, utilities for store-and-forward data exchange
   3 Copyright (C) 2016-2023 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         finished    bool
  86 }
  87
  88 func MTHSeqNew(size, offset int64) *MTHSeq {
  89         mth := MTHSeq{
  90                 hasherLeaf: blake3.New(MTHSize, MTHLeafKey[:]),
  91                 hasherNode: blake3.New(MTHSize, MTHNodeKey[:]),
  92                 buf:        bytes.NewBuffer(make([]byte, 0, 2*MTHBlockSize)),
  93         }
  94         if size == 0 {
  95                 return &mth
  96         }
  97         prepends := offset / MTHBlockSize
  98         toSkip := MTHBlockSize - (offset - prepends*MTHBlockSize)
  99         if toSkip == MTHBlockSize {
 100                 toSkip = 0
 101         } else if toSkip > 0 {
 102                 prepends++
 103         }
 104         prependSize := prepends * MTHBlockSize
 105         mth.ctr = prepends
 106         if prependSize > size {
 107                 prependSize = size
 108         }
 109         if offset+toSkip > size {
 110                 toSkip = size - offset
 111         }
 112         mth.size = size
 113         mth.prependSize = prependSize
 114         mth.toSkip = toSkip
 115         return &mth
 116 }
 117
 118 func (mth *MTHSeq) Reset() { panic("not implemented") }
 119
 120 func (mth *MTHSeq) Size() int { return MTHSize }
 121
 122 func (mth *MTHSeq) BlockSize() int { return MTHBlockSize }
 123
 124 func (mth *MTHSeq) PreaddFrom(r io.Reader, pktName string, showPrgrs bool) (int64, error) {
 125         if mth.finished {
 126                 return 0, errors.New("already Sum()ed")
 127         }
 128         if mth.buf.Len() > 0 {
 129                 if _, err := mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
 130                         panic(err)
 131                 }
 132                 mth.leafAdd()
 133                 mth.fold()
 134         }
 135         prevHashes := mth.hashes
 136         mth.hashes = nil
 137         prevCtr := mth.ctr
 138         mth.ctr = 0
 139         lr := io.LimitedReader{R: r, N: mth.prependSize}
 140         les := LEs{{"Pkt", pktName}, {"FullSize", mth.prependSize}}
 141         n, err := CopyProgressed(mth, &lr, "prehash", les, showPrgrs)
 142         for _, ent := range prevHashes {
 143                 mth.hashes = append(mth.hashes, ent)
 144                 mth.fold()
 145         }
 146         if mth.buf.Len() > 0 {
 147                 mth.ctr = prevCtr - 1
 148         } else {
 149                 mth.ctr = prevCtr
 150         }
 151         return n, err
 152 }
 153
 154 func (mth *MTHSeq) Events() chan MTHEvent {
 155         mth.events = make(chan MTHEvent)
 156         return mth.events
 157 }
 158
 159 func (mth *MTHSeq) PreaddSize() int64 { return mth.prependSize }
 160
 161 func (mth *MTHSeq) leafAdd() {
 162         ent := MTHSeqEnt{c: mth.ctr}
 163         mth.hasherLeaf.Sum(ent.h[:0])
 164         mth.hasherLeaf.Reset()
 165         mth.hashes = append(mth.hashes, ent)
 166         mth.ctr++
 167         if mth.events != nil {
 168                 mth.events <- MTHEvent{MTHEventAdd, &ent}
 169         }
 170 }
 171
 172 func (mth *MTHSeq) fold() {
 173         for len(mth.hashes) >= 2 {
 174                 hlen := len(mth.hashes)
 175                 end1 := &mth.hashes[hlen-2]
 176                 end0 := &mth.hashes[hlen-1]
 177                 if end1.c%2 == 1 {
 178                         break
 179                 }
 180                 if end1.l != end0.l {
 181                         break
 182                 }
 183                 if _, err := mth.hasherNode.Write(end1.h[:]); err != nil {
 184                         panic(err)
 185                 }
 186                 if _, err := mth.hasherNode.Write(end0.h[:]); err != nil {
 187                         panic(err)
 188                 }
 189                 mth.hashes = mth.hashes[:hlen-1]
 190                 end1.l++
 191                 end1.c /= 2
 192                 mth.hasherNode.Sum(end1.h[:0])
 193                 mth.hasherNode.Reset()
 194                 if mth.events != nil {
 195                         mth.events <- MTHEvent{MTHEventFold, end1}
 196                 }
 197         }
 198 }
 199
 200 func (mth *MTHSeq) Write(data []byte) (int, error) {
 201         if mth.finished {
 202                 return 0, errors.New("already Sum()ed")
 203         }
 204         n, err := mth.buf.Write(data)
 205         if err != nil {
 206                 return n, err
 207         }
 208         if mth.toSkip > 0 {
 209                 if int64(mth.buf.Len()) < mth.toSkip {
 210                         return n, err
 211                 }
 212                 mth.buf.Next(int(mth.toSkip))
 213                 mth.toSkip = 0
 214         }
 215         for mth.buf.Len() >= MTHBlockSize {
 216                 if _, err = mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
 217                         return n, err
 218                 }
 219                 mth.leafAdd()
 220                 mth.fold()
 221         }
 222         return n, err
 223 }
 224
 225 func (mth *MTHSeq) Sum(b []byte) []byte {
 226         if mth.finished {
 227                 return append(b, mth.hashes[0].h[:]...)
 228         }
 229         if mth.buf.Len() > 0 {
 230                 if _, err := mth.hasherLeaf.Write(mth.buf.Next(MTHBlockSize)); err != nil {
 231                         panic(err)
 232                 }
 233                 mth.leafAdd()
 234                 mth.fold()
 235         }
 236         switch mth.ctr {
 237         case 0:
 238                 if _, err := mth.hasherLeaf.Write(nil); err != nil {
 239                         panic(err)
 240                 }
 241                 mth.leafAdd()
 242                 fallthrough
 243         case 1:
 244                 ent := MTHSeqEnt{c: 1}
 245                 copy(ent.h[:], mth.hashes[0].h[:])
 246                 mth.ctr = 2
 247                 mth.hashes = append(mth.hashes, ent)
 248                 if mth.events != nil {
 249                         mth.events <- MTHEvent{MTHEventAdd, &ent}
 250                 }
 251                 mth.fold()
 252         }
 253         for len(mth.hashes) >= 2 {
 254                 hlen := len(mth.hashes)
 255                 end1 := &mth.hashes[hlen-2]
 256                 end0 := &mth.hashes[hlen-1]
 257                 end0.l = end1.l
 258                 end0.c = end1.c + 1
 259                 if mth.events != nil {
 260                         mth.events <- MTHEvent{MTHEventAdd, end0}
 261                 }
 262                 mth.fold()
 263         }
 264         mth.finished = true
 265         if mth.events != nil {
 266                 close(mth.events)
 267         }
 268         return append(b, mth.hashes[0].h[:]...)
 269 }
 270
 271 func MTHNew(size, offset int64) MTH {
 272         return MTHSeqNew(size, offset)
 273 }
 274
 275 // Some kind of reference implementation (fat, because eats memory)
 276
 277 type MTHFat struct {
 278         hasher *blake3.Hasher
 279         hashes [][MTHSize]byte
 280         buf    *bytes.Buffer
 281         events chan MTHEvent
 282 }
 283
 284 func MTHFatNew() *MTHFat {
 285         return &MTHFat{
 286                 hasher: blake3.New(MTHSize, MTHLeafKey[:]),
 287                 buf:    bytes.NewBuffer(make([]byte, 0, 2*MTHBlockSize)),
 288         }
 289 }
 290
 291 func (mth *MTHFat) Events() chan MTHEvent {
 292         mth.events = make(chan MTHEvent)
 293         return mth.events
 294 }
 295
 296 func (mth *MTHFat) Write(data []byte) (int, error) {
 297         n, err := mth.buf.Write(data)
 298         if err != nil {
 299                 return n, err
 300         }
 301         for mth.buf.Len() >= MTHBlockSize {
 302                 if _, err = mth.hasher.Write(mth.buf.Next(MTHBlockSize)); err != nil {
 303                         return n, err
 304                 }
 305                 h := new([MTHSize]byte)
 306                 mth.hasher.Sum(h[:0])
 307                 mth.hasher.Reset()
 308                 mth.hashes = append(mth.hashes, *h)
 309                 if mth.events != nil {
 310                         mth.events <- MTHEvent{
 311                                 MTHEventAdd,
 312                                 &MTHSeqEnt{
 313                                         0, int64(len(mth.hashes) - 1),
 314                                         mth.hashes[len(mth.hashes)-1],
 315                                 },
 316                         }
 317                 }
 318         }
 319         return n, err
 320 }
 321
 322 func (mth *MTHFat) Sum(b []byte) []byte {
 323         if mth.buf.Len() > 0 {
 324                 b := mth.buf.Next(MTHBlockSize)
 325                 if _, err := mth.hasher.Write(b); err != nil {
 326                         panic(err)
 327                 }
 328                 h := new([MTHSize]byte)
 329                 mth.hasher.Sum(h[:0])
 330                 mth.hasher.Reset()
 331                 mth.hashes = append(mth.hashes, *h)
 332                 if mth.events != nil {
 333                         mth.events <- MTHEvent{
 334                                 MTHEventAdd,
 335                                 &MTHSeqEnt{
 336                                         0, int64(len(mth.hashes) - 1),
 337                                         mth.hashes[len(mth.hashes)-1],
 338                                 },
 339                         }
 340                 }
 341         }
 342         switch len(mth.hashes) {
 343         case 0:
 344                 h := new([MTHSize]byte)
 345                 if _, err := mth.hasher.Write(nil); err != nil {
 346                         panic(err)
 347                 }
 348                 mth.hasher.Sum(h[:0])
 349                 mth.hasher.Reset()
 350                 mth.hashes = append(mth.hashes, *h)
 351                 if mth.events != nil {
 352                         mth.events <- MTHEvent{MTHEventAdd, &MTHSeqEnt{0, 0, mth.hashes[0]}}
 353                 }
 354                 fallthrough
 355         case 1:
 356                 mth.hashes = append(mth.hashes, mth.hashes[0])
 357                 if mth.events != nil {
 358                         mth.events <- MTHEvent{MTHEventAdd, &MTHSeqEnt{0, 1, mth.hashes[1]}}
 359                 }
 360         }
 361         mth.hasher = blake3.New(MTHSize, MTHNodeKey[:])
 362         level := 1
 363         for len(mth.hashes) != 1 {
 364                 hashesUp := make([][MTHSize]byte, 0, 1+len(mth.hashes)/2)
 365                 pairs := (len(mth.hashes) / 2) * 2
 366                 for i := 0; i < pairs; i += 2 {
 367                         if _, err := mth.hasher.Write(mth.hashes[i][:]); err != nil {
 368                                 panic(err)
 369                         }
 370                         if _, err := mth.hasher.Write(mth.hashes[i+1][:]); err != nil {
 371                                 panic(err)
 372                         }
 373                         h := new([MTHSize]byte)
 374                         mth.hasher.Sum(h[:0])
 375                         mth.hasher.Reset()
 376                         hashesUp = append(hashesUp, *h)
 377                         if mth.events != nil {
 378                                 mth.events <- MTHEvent{
 379                                         MTHEventFold,
 380                                         &MTHSeqEnt{
 381                                                 level, int64(len(hashesUp) - 1),
 382                                                 hashesUp[len(hashesUp)-1],
 383                                         },
 384                                 }
 385                         }
 386                 }
 387                 if len(mth.hashes)%2 == 1 {
 388                         hashesUp = append(hashesUp, mth.hashes[len(mth.hashes)-1])
 389                         if mth.events != nil {
 390                                 mth.events <- MTHEvent{
 391                                         MTHEventAdd,
 392                                         &MTHSeqEnt{
 393                                                 level, int64(len(hashesUp) - 1),
 394                                                 hashesUp[len(hashesUp)-1],
 395                                         },
 396                                 }
 397                         }
 398                 }
 399                 mth.hashes = hashesUp
 400                 level++
 401         }
 402         if mth.events != nil {
 403                 close(mth.events)
 404         }
 405         return append(b, mth.hashes[0][:]...)
 406 }