view release on metacpan or  search on metacpan

c-lib/s-bsdiff.c  view on Meta::CPAN

 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include "s-bsdipa-lib.h"

#include <assert.h>
#include <string.h>

#ifndef s_BSDIPA_SMALL
# define DIVSUFSORT_API static
# include "divsufsort.h"
#endif

/* Number of control block instances per s_bsdipa_ctrl_chunk */
#define a_BSDIPA_CTRL_NO 41

/* What seems a good default */
#ifndef s_BSDIPA_MAGIC_WINDOW
# define s_BSDIPA_MAGIC_WINDOW 16
#endif

#ifdef s_BSDIPA_SMALL
# define saidx_t s_bsdipa_off_t
#endif

/* */
#undef MIN
#define MIN(x,y) (((x) < (y)) ? (x) : (y))

/* With 32-bit off_t for now only s_BSDIPA_32 mode is supported */
#ifndef s_BSDIPA_32
# define OFF_MAX (sizeof(off_t) == 4 ? INT32_MAX : INT64_MAX)
typedef char ASSERTION_failed__off_max[OFF_MAX != INT32_MAX ? 1 : -1];
# undef OFF_MAX
#endif

/* Checks use saidx_t, but the patch code uses s_bsdipa_off_t, so these must be of EQ size! */
typedef char ASSERTION_failed__bsdipa_off_eq_saidx[sizeof(s_bsdipa_off_t) == sizeof(saidx_t) ? 1 : -1];

/* (Could be shared with s-bspatch.c) */
static void *a_bsdiff_alloc(void *vp, size_t size);
static void a_bsdiff_free(void *vp, void *dat);

static inline s_bsdipa_off_t a_bsdiff_matchlen(uint8_t const *aftdat, s_bsdipa_off_t aftlen,
		uint8_t const *befdat, s_bsdipa_off_t beflen);
static s_bsdipa_off_t a_bsdiff_search(s_bsdipa_off_t const *Ip, uint8_t const *aftdat, s_bsdipa_off_t aftlen,
		uint8_t const *befdat, s_bsdipa_off_t beflenp,
		s_bsdipa_off_t st, s_bsdipa_off_t en, s_bsdipa_off_t *posp);
static inline void a_bsdiff_xout(s_bsdipa_off_t x, uint8_t *bp);

/* Later imported original BSDiff suffix sort by Colin Percival; at EOF.
 * (It was replaced with libdivsufsort in the FreeBSD codebase to which he pointed me due to "existing fixes",
 * because of performance improvements: 10-15 percent for large binaries (megabytes); for smaller files his is better.)
 * Except for types and names i did not adapt syntax to my style for those. */
static void a_bsdiff_split(s_bsdipa_off_t *I, s_bsdipa_off_t *V, s_bsdipa_off_t start, s_bsdipa_off_t len,
		s_bsdipa_off_t h);
static int a_bsdiff_qsufsort(s_bsdipa_off_t *I, uint8_t const *aftdat, s_bsdipa_off_t aftlen,
		struct s_bsdipa_diff_ctx *dcp);

static void *
a_bsdiff_alloc(void *vp, size_t size){
	struct s_bsdipa_diff_ctx *dcp;

	dcp = (struct s_bsdipa_diff_ctx*)vp;
	vp = (*dcp->dc_mem.mc_alloc)(size);

	return vp;
}

static void
a_bsdiff_free(void *vp, void *dat){
	struct s_bsdipa_diff_ctx *dcp;

	dcp = (struct s_bsdipa_diff_ctx*)vp;
	(*dcp->dc_mem.mc_free)(dat);
}

static inline s_bsdipa_off_t
a_bsdiff_matchlen(uint8_t const *aftdat, s_bsdipa_off_t aftlen, uint8_t const *befdat, s_bsdipa_off_t beflen){
	s_bsdipa_off_t i;

	aftlen = MIN(aftlen, beflen);
	for(i = 0; i < aftlen; ++i)
		if(aftdat[i] != befdat[i])
			break;

	return i;
}

static s_bsdipa_off_t
a_bsdiff_search(s_bsdipa_off_t const *Ip, uint8_t const *aftdat, s_bsdipa_off_t aftlen,
		uint8_t const *befdat, s_bsdipa_off_t beflen,
		s_bsdipa_off_t st, s_bsdipa_off_t en, s_bsdipa_off_t *posp){
	s_bsdipa_off_t x, y, r;

	if(en - st < 2){
		x = a_bsdiff_matchlen(aftdat + Ip[st], aftlen - Ip[st], befdat, beflen);
		y = a_bsdiff_matchlen(aftdat + Ip[en], aftlen - Ip[en], befdat, beflen);

		if(x > y){
			*posp = Ip[st];
			r = x;
		}else{
			*posp = Ip[en];
			r = y;
		}
	}else{
		x = st + ((en - st) / 2);
		y = aftlen - Ip[x];
		y = MIN(y, beflen);
		if(memcmp(aftdat + Ip[x], befdat, y) < 0)
			r = a_bsdiff_search(Ip, aftdat, aftlen, befdat, beflen, x, en, posp);
		else