thodg/got/lib/delta.c

Branch : - branch - main - tag - 0.1 0.10 0.11 0.12 0.13 0.14 0.15 0.16 0.17 0.18 0.19 0.2 0.20 0.21 0.22 0.23 0.24 0.25 0.26 0.27 0.28 0.29 0.3 0.30 0.31 0.32 0.33 0.34 0.35 0.36 0.37 0.38 0.39 0.4 0.40 0.41 0.42 0.43 0.44 0.45 0.46 0.47 0.48 0.49 0.5 0.50 0.51 0.52 0.53 0.54 0.55 0.56 0.57 0.58 0.59 0.6 0.60 0.61 0.62 0.63 0.64 0.65 0.66 0.67 0.68 0.69 0.7 0.70 0.71 0.72 0.8 0.9

• Show log

  Commit

• Author : Stefan Sperling
  Date : 2018-04-01 15:57:43
  Hash : 72eb3431
  Message : look up deltas in the correct pack file

• lib/delta.c

• /*
   * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
   *
   * Permission to use, copy, modify, and distribute this software for any
   * purpose with or without fee is hereby granted, provided that the above
   * copyright notice and this permission notice appear in all copies.
   *
   * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
   * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
   * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
   * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
   * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
   * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
   */
  
  #include <sys/queue.h>
  
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #include <zlib.h>
  #include <sha1.h>
  
  #include "got_error.h"
  #include "got_repository.h"
  #include "got_object.h"
  
  #include "got_lib_delta.h"
  #include "got_lib_path.h"
  #include "got_lib_zbuf.h"
  
  #ifndef MIN
  #define	MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
  #endif
  
  struct got_delta *
  got_delta_open(const char *path_packfile, off_t offset, size_t tslen,
      int type, size_t size, off_t data_offset, uint8_t *delta_buf,
      size_t delta_len)
  {
  	struct got_delta *delta;
  
  	delta = calloc(1, sizeof(*delta));
  	if (delta == NULL)
  		return NULL;
  
  	delta->path_packfile = strdup(path_packfile);
  	if (delta->path_packfile == NULL) {
  		free(delta);
  		return NULL;
  	}
  	delta->type = type;
  	delta->offset = offset;
  	delta->tslen = tslen;
  	delta->size = size;
  	delta->data_offset = data_offset;
  	delta->delta_buf = delta_buf;
  	delta->delta_len = delta_len;
  	return delta;
  }
  
  void
  got_delta_close(struct got_delta *delta)
  {
  	free(delta->path_packfile);
  	free(delta->delta_buf);
  	free(delta);
  }
  
  const struct got_error *
  got_delta_chain_get_base_type(int *type, struct got_delta_chain *deltas)
  {
  	struct got_delta *delta;
  
  	/* The first delta in the chain should represent the base object. */
  	delta = SIMPLEQ_FIRST(&deltas->entries);
  	if (delta->type == GOT_OBJ_TYPE_COMMIT ||
  	    delta->type == GOT_OBJ_TYPE_TREE ||
  	    delta->type == GOT_OBJ_TYPE_BLOB ||
  	    delta->type == GOT_OBJ_TYPE_TAG) {
  		*type = delta->type;
  		return NULL;
  	}
  
  	return got_error(GOT_ERR_BAD_DELTA_CHAIN);
  }
  
  /* Fetch another (required) byte from the delta stream. */
  static const struct got_error *
  next_delta_byte(const uint8_t **p, size_t *remain)
  {
  	if (--(*remain) == 0)
  		return got_error(GOT_ERR_BAD_DELTA);
  	(*p)++;
  	return NULL;
  }
  
  static const struct got_error *
  parse_size(uint64_t *size, const uint8_t **p, size_t *remain)
  {
  	const struct got_error *err = NULL;
  	int i = 0;
  
  	*size = 0;
  	do {
  		/* We do not support size values which don't fit in 64 bit. */
  		if (i > 9)
  			return got_error(GOT_ERR_NO_SPACE);
  
  		if (i == 0)
  			*size = ((**p) & GOT_DELTA_SIZE_VAL_MASK);
  		else {
  			size_t shift = GOT_DELTA_SIZE_SHIFT * i;
  			*size |= (((**p) & GOT_DELTA_SIZE_VAL_MASK) << shift);
  		}
  
  		if (((**p) & GOT_DELTA_SIZE_MORE) == 0)
  			break;
  		i++;
  		err = next_delta_byte(p, remain);
  	} while (err == NULL);
  
  	return err;
  }
  
  static const struct got_error *
  parse_opcode(off_t *offset, size_t *len, const uint8_t **p, size_t *remain)
  {
  	const struct got_error *err = NULL;
  	off_t o = 0;
  	size_t l = 0;
  	uint8_t opcode = **p;
  
  	if (opcode & GOT_DELTA_COPY_OFF1) {
  		err = next_delta_byte(p, remain);
  		if (err)
  			return err;
  		o = (off_t)(**p);
  	}
  	if (opcode & GOT_DELTA_COPY_OFF2) {
  		err = next_delta_byte(p, remain);
  		if (err)
  			return err;
  		o |= ((off_t)(**p)) << 8;
  	}
  	if (opcode & GOT_DELTA_COPY_OFF3) {
  		err = next_delta_byte(p, remain);
  		if (err)
  			return err;
  		o |= ((off_t)(**p)) << 16;
  	}
  	if (opcode & GOT_DELTA_COPY_OFF4) {
  		err = next_delta_byte(p, remain);
  		if (err)
  			return err;
  		o |= ((off_t)(**p)) << 24;
  	}
  
  	if (opcode & GOT_DELTA_COPY_LEN1) {
  		err = next_delta_byte(p, remain);
  		if (err)
  			return err;
  		l = (off_t)(**p);
  	}
  	if (opcode & GOT_DELTA_COPY_LEN2) {
  		err = next_delta_byte(p, remain);
  		if (err)
  			return err;
  		l |= ((off_t)(**p)) << 8;
  	}
  	if (opcode & GOT_DELTA_COPY_LEN3) {
  		err = next_delta_byte(p, remain);
  		if (err)
  			return err;
  		l |= ((off_t)(**p)) << 16;
  	}
  
  	if (o == 0)
  		o = GOT_DELTA_COPY_DEFAULT_OFF;
  	if (l == 0)
  		l = GOT_DELTA_COPY_DEFAULT_LEN;
  
  	*offset = o;
  	*len = l;
  	return NULL;
  }
  
  static const struct got_error *
  copy_from_base(FILE *base_file, off_t offset, size_t size, FILE *outfile)
  {
  	if (fseeko(base_file, offset, SEEK_SET) != 0)
  		return got_error_from_errno();
  
  	while (size > 0) {
  		uint8_t data[2048];
  		size_t len = MIN(size, sizeof(data));
  		size_t n;
  
  		n = fread(data, len, 1, base_file);
  		if (n != 1)
  			return got_ferror(base_file, GOT_ERR_IO);
  
  		n = fwrite(data, len, 1, outfile);
  		if (n != 1)
  			return got_ferror(outfile, GOT_ERR_IO);
  
  		size -= len;
  	}
  
  	return NULL;
  }
  
  static const struct got_error *
  copy_from_delta(const uint8_t **p, size_t *remain, size_t len, FILE *outfile)
  {
  	size_t n;
  
  	if (*remain < len)
  		return got_error(GOT_ERR_BAD_DELTA);
  
  	n = fwrite(*p, len, 1, outfile);
  	if (n != 1)
  		return got_ferror(outfile, GOT_ERR_IO);
  
  	*p += len;
  	*remain -= len;
  	return NULL;
  }
  
  static const struct got_error *
  parse_delta_sizes(uint64_t *base_size, uint64_t *result_size,
      const uint8_t **p, size_t *remain)
  {
  	const struct got_error *err;
  
  	/* Read the two size fields at the beginning of the stream. */
  	err = parse_size(base_size, p, remain);
  	if (err)
  		return err;
  	err = next_delta_byte(p, remain);
  	if (err)
  		return err;
  	err = parse_size(result_size, p, remain);
  	if (err)
  		return err;
  
  	return NULL;
  }
  
  const struct got_error *
  got_delta_get_sizes(uint64_t *base_size, uint64_t *result_size,
      const uint8_t *delta_buf, size_t delta_len)
  {
  	size_t remain;
  	const uint8_t *p;
  
  	if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
  		return got_error(GOT_ERR_BAD_DELTA);
  
  	p = delta_buf;
  	remain = delta_len;
  	return parse_delta_sizes(base_size, result_size, &p, &remain);
  }
  
  const struct got_error *
  got_delta_apply_in_mem(uint8_t *base_buf, const uint8_t *delta_buf,
      size_t delta_len, uint8_t *outbuf, size_t *outsize)
  {
  	const struct got_error *err = NULL;
  	uint64_t base_size, result_size;
  	size_t remain;
  	const uint8_t *p;
  
  	*outsize= 0;
  
  	if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
  		return got_error(GOT_ERR_BAD_DELTA);
  
  	p = delta_buf;
  	remain = delta_len;
  	err = parse_delta_sizes(&base_size, &result_size, &p, &remain);
  	if (err)
  		return err;
  
  	/* Decode and execute copy instructions from the delta stream. */
  	err = next_delta_byte(&p, &remain);
  	while (err == NULL && remain > 0) {
  		if (*p & GOT_DELTA_BASE_COPY) {
  			off_t offset = 0;
  			size_t len = 0;
  			err = parse_opcode(&offset, &len, &p, &remain);
  			if (err)
  				break;
  			memcpy(outbuf + *outsize, base_buf + offset, len);
  			if (err == NULL) {
  				*outsize += len;
  				if (remain > 0) {
  					p++;
  					remain--;
  				}
  			}
  		} else {
  			size_t len = (size_t)*p;
  			if (len == 0) {
  				err = got_error(GOT_ERR_BAD_DELTA);
  				break;
  			}
  			err = next_delta_byte(&p, &remain);
  			if (err)
  				break;
  			if (remain < len)
  				return got_error(GOT_ERR_BAD_DELTA);
  			memcpy(outbuf + *outsize, p, len);
  			p += len;
  			remain -= len;
  			*outsize += len;
  		}
  	}
  
  	if (*outsize != result_size)
  		err = got_error(GOT_ERR_BAD_DELTA);
  	return err;
  }
  
  const struct got_error *
  got_delta_apply(FILE *base_file, const uint8_t *delta_buf,
      size_t delta_len, FILE *outfile, size_t *outsize)
  {
  	const struct got_error *err = NULL;
  	uint64_t base_size, result_size;
  	size_t remain = 0;
  	const uint8_t *p;
  	FILE *memstream = NULL;
  	char *memstream_buf = NULL;
  	size_t memstream_size = 0;
  
  	*outsize = 0;
  
  	if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
  		return got_error(GOT_ERR_BAD_DELTA);
  
  	p = delta_buf;
  	remain = delta_len;
  	err = parse_delta_sizes(&base_size, &result_size, &p, &remain);
  	if (err)
  		return err;
  
  	if (result_size < GOT_DELTA_RESULT_SIZE_CACHED_MAX)
  		memstream = open_memstream(&memstream_buf, &memstream_size);
  
  	/* Decode and execute copy instructions from the delta stream. */
  	err = next_delta_byte(&p, &remain);
  	while (err == NULL && remain > 0) {
  		if (*p & GOT_DELTA_BASE_COPY) {
  			off_t offset = 0;
  			size_t len = 0;
  			err = parse_opcode(&offset, &len, &p, &remain);
  			if (err)
  				break;
  			err = copy_from_base(base_file, offset, len,
  			    memstream ? memstream : outfile);
  			if (err == NULL) {
  				*outsize += len;
  				if (remain > 0) {
  					p++;
  					remain--;
  				}
  			}
  		} else {
  			size_t len = (size_t)*p;
  			if (len == 0) {
  				err = got_error(GOT_ERR_BAD_DELTA);
  				break;
  			}
  			err = next_delta_byte(&p, &remain);
  			if (err)
  				break;
  			err = copy_from_delta(&p, &remain, len,
  			    memstream ? memstream : outfile);
  			if (err == NULL)
  				*outsize += len;
  		}
  	}
  
  	if (*outsize != result_size)
  		err = got_error(GOT_ERR_BAD_DELTA);
  
  	if (memstream != NULL) {
  		fclose(memstream);
  		if (err == NULL) {
  			size_t n;
  			n = fwrite(memstream_buf, 1, memstream_size, outfile);
  			if (n != memstream_size)
  				err = got_ferror(outfile, GOT_ERR_IO);
  		}
  		free(memstream_buf);
  	}
  	if (err == NULL)
  		rewind(outfile);
  	return err;
  }