File: filefec.py

package info (click to toggle)
zfec 1.5.2-2.1
  • links: PTS, VCS
  • area: main
  • in suites: bookworm, bullseye, sid
  • size: 524 kB
  • sloc: python: 2,022; ansic: 892; haskell: 229; sh: 22; makefile: 4
file content (507 lines) | stat: -rw-r--r-- 17,941 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
from __future__ import print_function
import array, os, struct
from base64 import b32encode
from pyutil import fileutil
from pyutil.mathutil import pad_size, log_ceil

import zfec
from zfec import easyfec

CHUNKSIZE = 4096

def ab(x): # debuggery
    if len(x) >= 3:
        return "%s:%s" % (len(x), b32encode(x[-3:]),)
    elif len(x) == 2:
        return "%s:%s" % (len(x), b32encode(x[-2:]),)
    elif len(x) == 1:
        return "%s:%s" % (len(x), b32encode(x[-1:]),)
    elif len(x) == 0:
        return "%s:%s" % (len(x), "--empty--",)

class InsufficientShareFilesError(zfec.Error):
    def __init__(self, k, kb, *args, **kwargs):
        zfec.Error.__init__(self, *args, **kwargs)
        self.k = k
        self.kb = kb

    def __repr__(self):
        return "Insufficient share files -- %d share files are required to recover this file, but only %d were given" % (self.k, self.kb,)

    def __str__(self):
        return self.__repr__()

class CorruptedShareFilesError(zfec.Error):
    pass

def _build_header(m, k, pad, sh):
    """
    @param m: the total number of shares; 1 <= m <= 256
    @param k: the number of shares required to reconstruct; 1 <= k <= m
    @param pad: the number of bytes of padding added to the file before encoding; 0 <= pad < k
    @param sh: the shnum of this share; 0 <= k < m

    @return: a compressed string encoding m, k, pad, and sh
    """
    assert m >= 1
    assert m <= 2**8
    assert k >= 1
    assert k <= m
    assert pad >= 0
    assert pad < k

    assert sh >= 0
    assert sh < m

    bitsused = 0
    val = 0

    val |= (m - 1)
    bitsused += 8 # the first 8 bits always encode m

    kbits = log_ceil(m, 2) # num bits needed to store all possible values of k
    val <<= kbits
    bitsused += kbits

    val |= (k - 1)

    padbits = log_ceil(k, 2) # num bits needed to store all possible values of pad
    val <<= padbits
    bitsused += padbits

    val |= pad

    shnumbits = log_ceil(m, 2) # num bits needed to store all possible values of shnum
    val <<= shnumbits
    bitsused += shnumbits

    val |= sh

    assert bitsused >= 8, bitsused
    assert bitsused <= 32, bitsused

    if bitsused <= 16:
        val <<= (16-bitsused)
        cs = struct.pack('>H', val)
        assert cs[:-2] == b'\x00' * (len(cs)-2)
        return cs[-2:]
    if bitsused <= 24:
        val <<= (24-bitsused)
        cs = struct.pack('>I', val)
        assert cs[:-3] == b'\x00' * (len(cs)-3)
        return cs[-3:]
    else:
        val <<= (32-bitsused)
        cs = struct.pack('>I', val)
        assert cs[:-4] == b'\x00' * (len(cs)-4)
        return cs[-4:]

def MASK(bits):
    return (1<<bits)-1

def _parse_header(inf):
    """
    @param inf: an object which I can call read(1) on to get another byte

    @return: tuple of (m, k, pad, sh,); side-effect: the first one to four
        bytes of inf will be read
    """
    # The first 8 bits always encode m.
    ch = inf.read(1)
    if not ch:
        raise CorruptedShareFilesError("Share files were corrupted -- share file %r didn't have a complete metadata header at the front.  Perhaps the file was truncated." % (inf.name,))
    byte = ord(ch)
    m = byte + 1

    # The next few bits encode k.
    kbits = log_ceil(m, 2) # num bits needed to store all possible values of k
    b2_bits_left = 8-kbits
    kbitmask = MASK(kbits) << b2_bits_left
    ch = inf.read(1)
    if not ch:
        raise CorruptedShareFilesError("Share files were corrupted -- share file %r didn't have a complete metadata header at the front.  Perhaps the file was truncated." % (inf.name,))
    byte = ord(ch)
    k = ((byte & kbitmask) >> b2_bits_left) + 1

    shbits = log_ceil(m, 2) # num bits needed to store all possible values of shnum
    padbits = log_ceil(k, 2) # num bits needed to store all possible values of pad

    val = byte & (~kbitmask)

    needed_padbits = padbits - b2_bits_left
    if needed_padbits > 0:
        ch = inf.read(1)
        if not ch:
            raise CorruptedShareFilesError("Share files were corrupted -- share file %r didn't have a complete metadata header at the front.  Perhaps the file was truncated." % (inf.name,))
        byte = struct.unpack(">B", ch)[0]
        val <<= 8
        val |= byte
        needed_padbits -= 8
    assert needed_padbits <= 0
    extrabits = -needed_padbits
    pad = val >> extrabits
    val &= MASK(extrabits)

    needed_shbits = shbits - extrabits
    if needed_shbits > 0:
        ch = inf.read(1)
        if not ch:
            raise CorruptedShareFilesError("Share files were corrupted -- share file %r didn't have a complete metadata header at the front.  Perhaps the file was truncated." % (inf.name,))
        byte = struct.unpack(">B", ch)[0]
        val <<= 8
        val |= byte
        needed_shbits -= 8
    assert needed_shbits <= 0

    gotshbits = -needed_shbits

    sh = val >> gotshbits

    return (m, k, pad, sh,)

FORMAT_FORMAT = "%%s.%%0%dd_%%0%dd%%s"
RE_FORMAT = "%s.[0-9]+_[0-9]+%s"
def encode_to_files(inf, fsize, dirname, prefix, k, m, suffix=".fec", overwrite=False, verbose=False):
    """
    Encode inf, writing the shares to specially named, newly created files.

    @param fsize: calling read() on inf must yield fsize bytes of data and
        then raise an EOFError
    @param dirname: the name of the directory into which the sharefiles will
        be written
    """
    mlen = len(str(m))
    format = FORMAT_FORMAT % (mlen, mlen,)

    padbytes = pad_size(fsize, k)

    fns = []
    fs = []
    got_error = False
    try:
        for shnum in range(m):
            hdr = _build_header(m, k, padbytes, shnum)

            fn = os.path.join(dirname, format % (prefix, shnum, m, suffix,))
            if verbose:
                print("Creating share file %r..." % (fn,))
            if overwrite:
                f = open(fn, "wb")
            else:
                flags = os.O_WRONLY|os.O_CREAT|os.O_EXCL | (hasattr(os, 'O_BINARY') and os.O_BINARY)
                fd = os.open(fn, flags)
                f = os.fdopen(fd, "wb")
            fs.append(f)
            fns.append(fn)
            f.write(hdr)
        sumlen = [0]
        def cb(blocks, length):
            assert len(blocks) == len(fs)
            oldsumlen = sumlen[0]
            sumlen[0] += length
            if verbose:
                if int((float(oldsumlen) / fsize) * 10) != int((float(sumlen[0]) / fsize) * 10):
                    print(str(int((float(sumlen[0]) / fsize) * 10) * 10) + "% ...", end=" ")

            if sumlen[0] > fsize:
                raise IOError("Wrong file size -- possibly the size of the file changed during encoding.  Original size: %d, observed size at least: %s" % (fsize, sumlen[0],))
            for i in range(len(blocks)):
                data = blocks[i]
                fs[i].write(data)
                length -= len(data)

        encode_file_stringy_easyfec(inf, cb, k, m, chunksize=4096)
    except EnvironmentError as le:
        print("Cannot complete because of exception: ")
        print(le)
        got_error = True
    finally:
        for f in fs:
            f.close()
        if got_error:
            print("Cleaning up...")
            # clean up
            for fn in fns:
                if verbose:
                    print("Cleaning up: trying to remove %r..." % (fn,))
                fileutil.remove_if_possible(fn)
            return 1
    if verbose:
        print()
        print("Done!")
    return 0

# Note: if you really prefer base-2 and you change this code, then please
# denote 2^20 as "MiB" instead of "MB" in order to avoid ambiguity.  See:
# http://en.wikipedia.org/wiki/Megabyte
# Thanks.
MILLION_BYTES=10**6

def decode_from_files(outf, infiles, verbose=False):
    """
    Decode from the first k files in infiles, writing the results to outf.
    """
    assert len(infiles) >= 2
    infs = []
    shnums = []
    m = None
    k = None
    padlen = None

    byteswritten = 0
    for f in infiles:
        (nm, nk, npadlen, shnum,) = _parse_header(f)
        if not (m is None or m == nm):
            raise CorruptedShareFilesError("Share files were corrupted -- share file %r said that m was %s but another share file previously said that m was %s" % (f.name, nm, m,))
        m = nm
        if not (k is None or k == nk):
            raise CorruptedShareFilesError("Share files were corrupted -- share file %r said that k was %s but another share file previously said that k was %s" % (f.name, nk, k,))
        if not (k is None or k <= len(infiles)):
            raise InsufficientShareFilesError(k, len(infiles))
        k = nk
        if not (padlen is None or padlen == npadlen):
            raise CorruptedShareFilesError("Share files were corrupted -- share file %r said that pad length was %s but another share file previously said that pad length was %s" % (f.name, npadlen, padlen,))
        padlen = npadlen

        infs.append(f)
        shnums.append(shnum)

        if len(infs) == k:
            break

    dec = easyfec.Decoder(k, m)

    while True:
        chunks = [ inf.read(CHUNKSIZE) for inf in infs ]
        if [ch for ch in chunks if len(ch) != len(chunks[-1])]:
            raise CorruptedShareFilesError("Share files were corrupted -- all share files are required to be the same length, but they weren't.")

        if len(chunks[-1]) > 0:
            resultdata = dec.decode(chunks, shnums, padlen=0)
            outf.write(resultdata)
            byteswritten += len(resultdata)
            if verbose:
                if ((byteswritten - len(resultdata)) / (10*MILLION_BYTES)) != (byteswritten / (10*MILLION_BYTES)):
                    print(str(byteswritten / MILLION_BYTES) + " MB ...", end=" ")
        else:
            if padlen > 0:
                outf.truncate(byteswritten - padlen)
            return # Done.
    if verbose:
        print()
        print("Done!")

def encode_file(inf, cb, k, m, chunksize=4096):
    """
    Read in the contents of inf, encode, and call cb with the results.

    First, k "input blocks" will be read from inf, each input block being of
    size chunksize.  Then these k blocks will be encoded into m "result
    blocks".  Then cb will be invoked, passing a list of the m result blocks
    as its first argument, and the length of the encoded data as its second
    argument.  (The length of the encoded data is always equal to k*chunksize,
    until the last iteration, when the end of the file has been reached and
    less than k*chunksize bytes could be read from the file.)  This procedure
    is iterated until the end of the file is reached, in which case the space
    of the input blocks that is unused is filled with zeroes before encoding.

    Note that the sequence passed in calls to cb() contains mutable array
    objects in its first k elements whose contents will be overwritten when
    the next segment is read from the input file.  Therefore the
    implementation of cb() has to either be finished with those first k arrays
    before returning, or if it wants to keep the contents of those arrays for
    subsequent use after it has returned then it must make a copy of them to
    keep.

    @param inf the file object from which to read the data
    @param cb the callback to be invoked with the results
    @param k the number of shares required to reconstruct the file
    @param m the total number of shares created
    @param chunksize how much data to read from inf for each of the k input
        blocks
    """
    enc = zfec.Encoder(k, m)
    l = tuple([ array.array('c') for i in range(k) ])
    indatasize = k*chunksize # will be reset to shorter upon EOF
    eof = False
    ZEROES=array.array('c', ['\x00'])*chunksize
    while not eof:
        # This loop body executes once per segment.
        i = 0
        while (i<len(l)):
            # This loop body executes once per chunk.
            a = l[i]
            del a[:]
            try:
                a.fromfile(inf, chunksize)
                i += 1
            except EOFError:
                eof = True
                indatasize = i*chunksize + len(a)

                # padding
                a.fromstring("\x00" * (chunksize-len(a)))
                i += 1
                while (i<len(l)):
                    a = l[i]
                    a[:] = ZEROES
                    i += 1

        res = enc.encode(l)
        cb(res, indatasize)

try:
    from hashlib import sha1
    sha1 = sha1 # hush pyflakes
except ImportError:
    # hashlib was added in Python 2.5.0.
    import sha
    sha1 = sha

def encode_file_not_really(inf, cb, k, m, chunksize=4096):
    enc = zfec.Encoder(k, m)
    l = tuple([ array.array('c') for i in range(k) ])
    indatasize = k*chunksize # will be reset to shorter upon EOF
    eof = False
    ZEROES=array.array('c', ['\x00'])*chunksize
    while not eof:
        # This loop body executes once per segment.
        i = 0
        while (i<len(l)):
            # This loop body executes once per chunk.
            a = l[i]
            del a[:]
            try:
                a.fromfile(inf, chunksize)
                i += 1
            except EOFError:
                eof = True
                indatasize = i*chunksize + len(a)

                # padding
                a.fromstring("\x00" * (chunksize-len(a)))
                i += 1
                while (i<len(l)):
                    a = l[i]
                    a[:] = ZEROES
                    i += 1

        # res = enc.encode(l)
        cb(None, None)

def encode_file_not_really_and_hash(inf, cb, k, m, chunksize=4096):
    hasher = sha1.new()
    enc = zfec.Encoder(k, m)
    l = tuple([ array.array('c') for i in range(k) ])
    indatasize = k*chunksize # will be reset to shorter upon EOF
    eof = False
    ZEROES=array.array('c', ['\x00'])*chunksize
    while not eof:
        # This loop body executes once per segment.
        i = 0
        while (i<len(l)):
            # This loop body executes once per chunk.
            a = l[i]
            del a[:]
            try:
                a.fromfile(inf, chunksize)
                i += 1
            except EOFError:
                eof = True
                indatasize = i*chunksize + len(a)

                # padding
                a.fromstring("\x00" * (chunksize-len(a)))
                i += 1
                while (i<len(l)):
                    a = l[i]
                    a[:] = ZEROES
                    i += 1

        # res = enc.encode(l)
        for thing in l:
            hasher.update(thing)
        cb(None, None)

def encode_file_stringy(inf, cb, k, m, chunksize=4096):
    """
    Read in the contents of inf, encode, and call cb with the results.

    First, k "input blocks" will be read from inf, each input block being of
    size chunksize.  Then these k blocks will be encoded into m "result
    blocks".  Then cb will be invoked, passing a list of the m result blocks
    as its first argument, and the length of the encoded data as its second
    argument.  (The length of the encoded data is always equal to k*chunksize,
    until the last iteration, when the end of the file has been reached and
    less than k*chunksize bytes could be read from the file.)  This procedure
    is iterated until the end of the file is reached, in which case the part
    of the input shares that is unused is filled with zeroes before encoding.

    @param inf the file object from which to read the data
    @param cb the callback to be invoked with the results
    @param k the number of shares required to reconstruct the file
    @param m the total number of shares created
    @param chunksize how much data to read from inf for each of the k input
        blocks
    """
    enc = zfec.Encoder(k, m)
    indatasize = k*chunksize # will be reset to shorter upon EOF
    while indatasize == k*chunksize:
        # This loop body executes once per segment.
        i = 0
        l = []
        ZEROES = b'\x00'*chunksize
        while i<k:
            # This loop body executes once per chunk.
            i += 1
            l.append(inf.read(chunksize))
            if len(l[-1]) < chunksize:
                indatasize = i*chunksize + len(l[-1])

                # padding
                l[-1] = l[-1] + b"\x00" * (chunksize-len(l[-1]))
                while i<k:
                    l.append(ZEROES)
                    i += 1

        res = enc.encode(l)
        cb(res, indatasize)

def encode_file_stringy_easyfec(inf, cb, k, m, chunksize=4096):
    """
    Read in the contents of inf, encode, and call cb with the results.

    First, chunksize*k bytes will be read from inf, then encoded into m
    "result blocks".  Then cb will be invoked, passing a list of the m result
    blocks as its first argument, and the length of the encoded data as its
    second argument.  (The length of the encoded data is always equal to
    k*chunksize, until the last iteration, when the end of the file has been
    reached and less than k*chunksize bytes could be read from the file.)
    This procedure is iterated until the end of the file is reached, in which
    case the space of the input that is unused is filled with zeroes before
    encoding.

    @param inf the file object from which to read the data
    @param cb the callback to be invoked with the results
    @param k the number of shares required to reconstruct the file
    @param m the total number of shares created
    @param chunksize how much data to read from inf for each of the k input
        blocks
    """
    enc = easyfec.Encoder(k, m)

    readsize = k*chunksize
    indata = inf.read(readsize)
    while indata:
        res = enc.encode(indata)
        cb(res, len(indata))
        indata = inf.read(readsize)

# zfec -- fast forward error correction library with Python interface
#
# Copyright (C) 2007-2010 Allmydata, Inc.
# Author: Zooko Wilcox-O'Hearn
#
# This file is part of zfec.
#
# See README.rst for licensing information.