lib/got_lib_delta.h

   1 /*
   2  * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 struct got_delta {
  18         STAILQ_ENTRY(got_delta) entry;
  19         off_t offset;
  20         size_t tslen;
  21         int type;
  22         size_t size;
  23         off_t data_offset;
  24 };
  25
  26 struct got_delta_chain {
  27         int nentries;
  28         STAILQ_HEAD(, got_delta) entries;
  29 };
  30
  31 #define GOT_DELTA_CHAIN_RECURSION_MAX   500
  32
  33 struct got_delta *got_delta_open(off_t, size_t, int, size_t, off_t);
  34 const struct got_error *got_delta_chain_get_base_type(int *,
  35     struct got_delta_chain *);
  36 const struct got_error *got_delta_get_sizes(uint64_t *, uint64_t *,
  37     const uint8_t *, size_t);
  38 const struct got_error *got_delta_apply_in_mem(uint8_t *, size_t,
  39     const uint8_t *, size_t, uint8_t *, size_t *, size_t);
  40 const struct got_error *got_delta_apply(FILE *, const uint8_t *, size_t,
  41     FILE *, size_t *);
  42
  43 /*
  44  * The amount of result data we may keep in RAM while applying deltas.
  45  * Data larger than this is written to disk during delta application (slow).
  46  */
  47 #define GOT_DELTA_RESULT_SIZE_CACHED_MAX        (8 * 1024 * 1024) /* bytes */
  48
  49 /*
  50  * Definitions for delta data streams.
  51  */
  52
  53 #define GOT_DELTA_STREAM_LENGTH_MIN     4       /* bytes */
  54
  55 /*
  56  * A delta stream begins with two size fields. The first specifies the
  57  * size of the delta base, and the second describes the expected size of
  58  * the data which results from applying the delta to the delta base.
  59  *
  60  * Each size field uses a variable length encoding:
  61  * size0...sizeN form a 7+7+7+...+7 bit integer, where size0 is the
  62  * least significant part and sizeN is the most significant part.
  63  * If the MSB of a size byte is set, an additional size byte follows.
  64  */
  65 #define GOT_DELTA_SIZE_VAL_MASK 0x7f
  66 #define GOT_DELTA_SIZE_SHIFT    7
  67 #define GOT_DELTA_SIZE_MORE     0x80
  68
  69 /*
  70  * The rest of the delta stream contains copy instructions.
  71  *
  72  * A base copy instruction copies N bytes starting at offset X from the delta
  73  * base to the output. Base copy instructions begin with a byte which has its
  74  * MSB set. The remaining bits of this byte describe how many offset and
  75  * length value bytes follow.
  76  * The offset X is encoded in 1 to 4 bytes, and the length N is encoded in
  77  * 1 to 3 bytes. For both values, the first byte contributes the least
  78  * significant part and the last byte which is present contributes the
  79  * most significant part.
  80  * If the offset value is omitted, an offset of zero is implied.
  81  * If the length value is omitted, a default length of 65536 bytes is implied.
  82  *
  83  * An inline copy instruction copies data from the delta stream to the output.
  84  * Such instructions begin with one byte which does not have the MSB set
  85  * and which specifies the length of the inline data which follows (i.e.
  86  * at most 127 bytes). A length value of zero is invalid.
  87  */
  88
  89 #define GOT_DELTA_BASE_COPY     0x80
  90
  91 #define GOT_DELTA_COPY_OFF1     0x01    /* byte 1 of offset is present */
  92 #define GOT_DELTA_COPY_OFF2     0x02    /* byte 2 of offset is present */
  93 #define GOT_DELTA_COPY_OFF3     0x04    /* byte 3 of offset is present */
  94 #define GOT_DELTA_COPY_OFF4     0x08    /* byte 4 of offset is present */
  95
  96 #define GOT_DELTA_COPY_LEN1     0x10    /* byte 1 of length is present */
  97 #define GOT_DELTA_COPY_LEN2     0x20    /* byte 2 of length is present */
  98 #define GOT_DELTA_COPY_LEN3     0x40    /* byte 3 of length is present */
  99
 100 #define GOT_DELTA_COPY_DEFAULT_OFF      0x0     /* default offset if omitted */
 101 #define GOT_DELTA_COPY_DEFAULT_LEN      0x10000 /* default length if omitted */