gbdk-2020 | GameBoy Development Kit |
| download: https://git.y1.nz/archives/gbdk.tar.gz | |
| README | Files | Log | Refs | LICENSE |
gbdk-support/gbcompress/zx0/zx0_shrink.c
1 /*
2 * shrink.c - compressor implementation
3 *
4 * Copyright (C) 2021 Emmanuel Marty
5 *
6 * This software is provided 'as-is', without any express or implied
7 * warranty. In no event will the authors be held liable for any damages
8 * arising from the use of this software.
9 *
10 * Permission is granted to anyone to use this software for any purpose,
11 * including commercial applications, and to alter it and redistribute it
12 * freely, subject to the following restrictions:
13 *
14 * 1. The origin of this software must not be misrepresented; you must not
15 * claim that you wrote the original software. If you use this software
16 * in a product, an acknowledgment in the product documentation would be
17 * appreciated but is not required.
18 * 2. Altered source versions must be plainly marked as such, and must not be
19 * misrepresented as being the original software.
20 * 3. This notice may not be removed or altered from any source distribution.
21 */
22
23 /*
24 * Uses the libdivsufsort library Copyright (c) 2003-2008 Yuta Mori
25 *
26 * Implements the ZX0 encoding designed by Einar Saukas. https://github.com/einar-saukas/ZX0
27 * Also inspired by Charles Bloom's compression blog. http://cbloomrants.blogspot.com/
28 *
29 */
30
31 #include <stdlib.h>
32 #include <string.h>
33 #include <limits.h>
34 #include "zx0_libsalvador.h"
35 #include "zx0_matchfinder.h"
36 #include "zx0_shrink.h"
37 #include "zx0_format.h"
38
39 #define MIN_ENCODED_MATCH_SIZE 2
40 #define TOKEN_SIZE 1
41 #define OFFSET_COST(__offset) (((__offset) <= 128) ? 8 : (7 + salvador_get_elias_size((((__offset) - 1) >> 7) + 1)))
42
43 /** Costs, per length */
44 static const char salvador_cost_for_len[8192] = {
45 0, 2, 4, 4, 6, 6, 6, 6, 8, 8, 8, 8, 8, 8, 8, 8, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
46 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
47 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
48 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
49 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
50 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
51 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
52 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
53 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
54 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
55 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
56 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
57 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
58 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
59 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
60 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
61 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
62 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
63 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
64 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
65 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
66 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
67 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
68 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
69 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
70 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
71 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
72 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
73 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
74 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
75 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
76 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
77 };
78
79 /**
80 * Get the number of bits required to encode a gamma value
81 *
82 * @param nValue value to encode as gamma
83 *
84 * @return number of bits required for encoding
85 */
86 static int salvador_get_elias_size(const int nValue) {
87 if (nValue >= 0 && nValue < 8192) {
88 return salvador_cost_for_len[nValue] - TOKEN_SIZE;
89 }
90 else {
91 int i = nValue;
92 int nBits = 0;
93
94 i |= (i >> 1);
95 i |= (i >> 2);
96 i |= (i >> 4);
97 i |= (i >> 8);
98 i |= (i >> 16);
99 i = (i - (i >> 1));
100
101 while ((i >>= 1) > 0) {
102 nBits++;
103 nBits++;
104 }
105
106 nBits++;
107
108 return nBits;
109 }
110 }
111
112 /**
113 * Write packed 0 control bit to output (compressed) buffer
114 *
115 * @param pOutData pointer to output buffer
116 * @param nOutOffset current write index into output buffer
117 * @param nMaxOutDataSize maximum size of output buffer, in bytes
118 * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits
119 * @param nCurBitShift bit shift count
120 *
121 * @return updated write index into output buffer, or -1 in case of an error
122 */
123 static int salvador_write_zero_ctrl_bit(unsigned char *pOutData, int nOutOffset, const int nMaxOutDataSize, int *nCurBitsOffset, int *nCurBitShift) {
124 if (nOutOffset >= 0) {
125 if ((*nCurBitShift) == -1) {
126 /* Allocate a new byte in the stream to pack bits in */
127 if (nOutOffset >= nMaxOutDataSize) return -1;
128 (*nCurBitsOffset) = nOutOffset;
129 (*nCurBitShift) = 7;
130 pOutData[nOutOffset++] = 0;
131 }
132
133 (*nCurBitShift)--;
134 }
135
136 return nOutOffset;
137 }
138
139 /**
140 * Write packed 1 control bit to output (compressed) buffer
141 *
142 * @param pOutData pointer to output buffer
143 * @param nOutOffset current write index into output buffer
144 * @param nMaxOutDataSize maximum size of output buffer, in bytes
145 * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits
146 * @param nCurBitShift bit shift count
147 *
148 * @return updated write index into output buffer, or -1 in case of an error
149 */
150 static int salvador_write_one_ctrl_bit(unsigned char* pOutData, int nOutOffset, const int nMaxOutDataSize, int* nCurBitsOffset, int* nCurBitShift) {
151 if (nOutOffset >= 0) {
152 if ((*nCurBitShift) == -1) {
153 /* Allocate a new byte in the stream to pack bits in */
154 if (nOutOffset >= nMaxOutDataSize) return -1;
155 (*nCurBitsOffset) = nOutOffset;
156 (*nCurBitShift) = 7;
157 pOutData[nOutOffset++] = 0;
158 }
159
160 pOutData[(*nCurBitsOffset)] |= 1 << ((*nCurBitShift)--);
161 }
162
163 return nOutOffset;
164 }
165
166 /**
167 * Write packed data bit to output (compressed) buffer
168 *
169 * @param pOutData pointer to output buffer
170 * @param nOutOffset current write index into output buffer
171 * @param nMaxOutDataSize maximum size of output buffer, in bytes
172 * @param nValue bit value to write
173 * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits
174 * @param nCurBitShift bit shift count
175 *
176 * @return updated write index into output buffer, or -1 in case of an error
177 */
178 static int salvador_write_data_bit(unsigned char* pOutData, const int nOutOffset, const int nMaxOutDataSize, const int nValue, const int* nCurBitsOffset, int* nCurBitShift) {
179 if (nOutOffset >= 0) {
180 pOutData[(*nCurBitsOffset)] |= nValue << ((*nCurBitShift)--);
181 }
182
183 return nOutOffset;
184 }
185
186 /**
187 * Write normally encoded, interlaced elias gamma value to output (compressed) buffer
188 *
189 * @param pOutData pointer to output buffer
190 * @param nOutOffset current write index into output buffer
191 * @param nMaxOutDataSize maximum size of output buffer, in bytes
192 * @param nValue value to write with gamma encoding
193 * @param nBackward 1 for backward compression, 0 for forward compression
194 * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits
195 * @param nCurBitShift bit shift count
196 *
197 * @return updated write index into output buffer, or -1 in case of an error
198 */
199 static int salvador_write_normal_elias_value(unsigned char* pOutData, int nOutOffset, const int nMaxOutDataSize, const int nValue, const int nBackward, int* nCurBitsOffset, int* nCurBitShift) {
200 int i = nValue;
201
202 i |= (i >> 1);
203 i |= (i >> 2);
204 i |= (i >> 4);
205 i |= (i >> 8);
206 i |= (i >> 16);
207 i = (i - (i >> 1));
208
209 if (nBackward) {
210 while ((i >>= 1) > 0) {
211 nOutOffset = salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
212 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 1 : 0, nCurBitsOffset, nCurBitShift);
213 }
214
215 return salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
216 }
217 else {
218 while ((i >>= 1) > 0) {
219 nOutOffset = salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
220 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 1 : 0, nCurBitsOffset, nCurBitShift);
221 }
222
223 return salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
224 }
225 }
226
227 /**
228 * Write inverted, interlaced elias gamma value to output (compressed) buffer
229 *
230 * @param pOutData pointer to output buffer
231 * @param nOutOffset current write index into output buffer
232 * @param nMaxOutDataSize maximum size of output buffer, in bytes
233 * @param nValue value to write with gamma encoding
234 * @param nBackward 1 for backward compression, 0 for forward compression
235 * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits
236 * @param nCurBitShift bit shift count
237 *
238 * @return updated write index into output buffer, or -1 in case of an error
239 */
240 static int salvador_write_inverted_elias_value(unsigned char* pOutData, int nOutOffset, const int nMaxOutDataSize, const int nValue, const int nBackward, int* nCurBitsOffset, int* nCurBitShift) {
241 int i = nValue;
242
243 i |= (i >> 1);
244 i |= (i >> 2);
245 i |= (i >> 4);
246 i |= (i >> 8);
247 i |= (i >> 16);
248 i = (i - (i >> 1));
249
250 if (nBackward) {
251 while ((i >>= 1) > 0) {
252 nOutOffset = salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
253 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 0 : 1, nCurBitsOffset, nCurBitShift);
254 }
255
256 return salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
257 }
258 else {
259 while ((i >>= 1) > 0) {
260 nOutOffset = salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
261 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 0 : 1, nCurBitsOffset, nCurBitShift);
262 }
263
264 return salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
265 }
266 }
267
268 /**
269 * Write elias gamma encoded value to output (compressed) buffer, with the first bit stored in a different (match offset) byte
270 *
271 * @param pOutData pointer to output buffer
272 * @param nOutOffset current write index into output buffer
273 * @param nMaxOutDataSize maximum size of output buffer, in bytes
274 * @param nValue value to write with gamma encoding
275 * @param nBackward 1 for backward compression, 0 for forward compression
276 * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits
277 * @param nCurBitShift bit shift count
278 *
279 * @return updated write index into output buffer, or -1 in case of an error
280 */
281 static int salvador_write_split_elias_value(unsigned char* pOutData, int nOutOffset, const int nMaxOutDataSize, const int nValue, const int nBackward, int* nCurBitsOffset, int* nCurBitShift) {
282 int i = nValue;
283
284 i |= (i >> 1);
285 i |= (i >> 2);
286 i |= (i >> 4);
287 i |= (i >> 8);
288 i |= (i >> 16);
289 i = (i - (i >> 1));
290
291 i >>= 1;
292 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 1 : 0, nCurBitsOffset, nCurBitShift);
293
294 if (nBackward) {
295 while ((i >>= 1) > 0) {
296 nOutOffset = salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
297 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 1 : 0, nCurBitsOffset, nCurBitShift);
298 }
299
300 return salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
301 }
302 else {
303 while ((i >>= 1) > 0) {
304 nOutOffset = salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
305 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 1 : 0, nCurBitsOffset, nCurBitShift);
306 }
307
308 return salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift);
309 }
310 }
311
312 /**
313 * Get the number of extra bits required to represent a literals length
314 *
315 * @param nLength literals length
316 *
317 * @return number of extra bits required
318 */
319 static inline int salvador_get_literals_varlen_size(const int nLength) {
320 if (nLength >= 0 && nLength < 8192)
321 return salvador_cost_for_len[nLength];
322 else
323 return TOKEN_SIZE + salvador_get_elias_size(nLength);
324 }
325
326 /**
327 * Get the number of extra bits required to represent a non-rep match length
328 *
329 * @param __nLength actual match length
330 *
331 * @return number of extra bits required
332 */
333 #define salvador_get_match_varlen_size_norep(__nLength) salvador_get_elias_size((__nLength) - 1)
334
335 /**
336 * Get the number of extra bits required to represent a repmatch length
337 *
338 * @param __nLength actual match length
339 *
340 * @return number of extra bits required
341 */
342 #define salvador_get_match_varlen_size_rep(__nLength) salvador_get_elias_size(__nLength)
343
344 /**
345 * Insert forward rep candidate
346 *
347 * @param pCompressor compression context
348 * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress)
349 * @param i input data window position whose matches are being considered
350 * @param nMatchOffset match offset to use as rep candidate
351 * @param nStartOffset current offset in input window (typically the number of previously compressed bytes)
352 * @param nEndOffset offset to end finding matches at (typically the size of the total input window in bytes
353 * @param nDepth current insertion depth
354 */
355 static void salvador_insert_forward_match(salvador_compressor *pCompressor, const unsigned char *pInWindow, const int i, const int nMatchOffset, const int nStartOffset, const int nEndOffset, const int nDepth) {
356 const salvador_arrival *arrival = pCompressor->arrival + ((i - nStartOffset) * pCompressor->max_arrivals_per_position);
357 const int *rle_len = (const int*)pCompressor->intervals /* reuse */;
358 salvador_visited* visited = ((salvador_visited*)pCompressor->pos_data) - nStartOffset /* reuse */;
359 int j;
360
361 for (j = 0; j < NINITIAL_ARRIVALS_PER_POSITION && arrival[j].from_slot; j++) {
362 if (arrival[j].num_literals) {
363 const int nRepOffset = arrival[j].rep_offset;
364
365 if (nMatchOffset != nRepOffset) {
366 const int nRepPos = arrival[j].rep_pos;
367
368 if (nRepPos >= nStartOffset &&
369 nRepPos < nEndOffset &&
370 visited[nRepPos] != nMatchOffset) {
371
372 visited[nRepPos] = nMatchOffset;
373
374 salvador_match* fwd_match = pCompressor->match + ((nRepPos - nStartOffset) * NMATCHES_PER_INDEX);
375
376 if (fwd_match[NMATCHES_PER_INDEX - 1].length == 0) {
377 if (nRepPos >= nMatchOffset) {
378 const unsigned char* pInWindowStart = pInWindow + nRepPos;
379
380 if (pInWindowStart[0] == pInWindowStart[-nMatchOffset]) {
381 if (nRepOffset) {
382 unsigned int nMaxRepLen = nEndOffset - nRepPos;
383
384 if (nMaxRepLen > LCP_MAX)
385 nMaxRepLen = LCP_MAX;
386 const unsigned char* pInWindowMax = pInWindowStart + nMaxRepLen;
387
388 const int nLen0 = rle_len[nRepPos - nMatchOffset];
389 const int nLen1 = rle_len[nRepPos];
390 unsigned int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1, r;
391
392 for (r = 0; fwd_match[r].length; r++) {
393 if (fwd_match[r].offset == nMatchOffset) {
394 if (nMinLen < fwd_match[r].length)
395 nMinLen = fwd_match[r].length;
396 break;
397 }
398 }
399
400 const unsigned char* pInWindowAtRepOffset = pInWindowStart + nMinLen;
401
402 if (pInWindowAtRepOffset > pInWindowMax)
403 pInWindowAtRepOffset = pInWindowMax;
404
405 while ((pInWindowAtRepOffset + 8) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nMatchOffset, 8))
406 pInWindowAtRepOffset += 8;
407 while ((pInWindowAtRepOffset + 4) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nMatchOffset, 4))
408 pInWindowAtRepOffset += 4;
409 while (pInWindowAtRepOffset < pInWindowMax && pInWindowAtRepOffset[0] == pInWindowAtRepOffset[-nMatchOffset])
410 pInWindowAtRepOffset++;
411
412 const unsigned short nCurRepLen = (const unsigned short)(pInWindowAtRepOffset - pInWindowStart);
413 unsigned short* fwd_depth = pCompressor->match_depth + ((nRepPos - nStartOffset) * NMATCHES_PER_INDEX);
414
415 if (!fwd_match[r].length) {
416 fwd_match[r].length = nCurRepLen;
417 fwd_match[r].offset = nMatchOffset;
418 fwd_depth[r] = 0;
419
420 if (nDepth < 9)
421 salvador_insert_forward_match(pCompressor, pInWindow, nRepPos, nMatchOffset, nStartOffset, nEndOffset, nDepth + 1);
422 }
423 else {
424 if (fwd_match[r].length < nCurRepLen && fwd_depth[r] == 0) {
425 fwd_match[r].length = nCurRepLen;
426 }
427 }
428 }
429 }
430 }
431 }
432 }
433 }
434 }
435 }
436 }
437
438 /**
439 * Attempt to pick optimal matches, so as to produce the smallest possible output that decompresses to the same input
440 *
441 * @param pCompressor compression context
442 * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress)
443 * @param nStartOffset current offset in input window (typically the number of previously compressed bytes)
444 * @param nEndOffset offset to end finding matches at (typically the size of the total input window in bytes
445 * @param nInsertForwardReps non-zero to insert forward repmatch candidates, zero to use the previously inserted candidates
446 * @param nCurRepMatchOffset starting rep offset for this block
447 * @param nArrivalsPerPosition number of arrivals to record per input buffer position
448 * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise
449 */
450 static void salvador_optimize_forward(salvador_compressor *pCompressor, const unsigned char *pInWindow, const int nStartOffset, const int nEndOffset, const int nInsertForwardReps, const int *nCurRepMatchOffset, const int nArrivalsPerPosition, const int nBlockFlags) {
451 const int nMaxArrivalsPerPosition = pCompressor->max_arrivals_per_position;
452 salvador_arrival *arrival = pCompressor->arrival - (nStartOffset * nMaxArrivalsPerPosition);
453 const int* rle_len = (const int*)pCompressor->intervals /* reuse */;
454 salvador_arrival* cur_arrival;
455 int i;
456
457 if ((nEndOffset - nStartOffset) > pCompressor->block_size) return;
458
459 for (i = (nStartOffset * nMaxArrivalsPerPosition); i != ((nEndOffset + 1) * nMaxArrivalsPerPosition); i += nMaxArrivalsPerPosition) {
460 int j;
461
462 memset(arrival + i, 0, sizeof(salvador_arrival) * nMaxArrivalsPerPosition);
463
464 for (j = 0; j < nMaxArrivalsPerPosition; j++)
465 arrival[i + j].cost = 0x40000000;
466 }
467
468 arrival[nStartOffset * nMaxArrivalsPerPosition].cost = 0;
469 arrival[nStartOffset * nMaxArrivalsPerPosition].from_slot = -1;
470 arrival[nStartOffset * nMaxArrivalsPerPosition].rep_offset = *nCurRepMatchOffset;
471
472 if (nInsertForwardReps) {
473 salvador_visited* visited = ((salvador_visited*)pCompressor->pos_data) - nStartOffset /* reuse */;
474
475 memset(visited + nStartOffset, 0, (nEndOffset - nStartOffset) * sizeof(salvador_visited));
476 }
477
478 for (i = nStartOffset, cur_arrival = &arrival[nStartOffset * nMaxArrivalsPerPosition]; i != nEndOffset; i++, cur_arrival += nMaxArrivalsPerPosition) {
479 salvador_arrival *pDestLiteralSlots = &cur_arrival[nMaxArrivalsPerPosition];
480 int j, m;
481
482 for (j = 0; j < nArrivalsPerPosition && cur_arrival[j].from_slot; j++) {
483 const int nNumLiterals = cur_arrival[j].num_literals + 1;
484 const int nCodingChoiceCost = cur_arrival[j].cost + 8 /* literal */ + (((nNumLiterals & (nNumLiterals - 1)) == 0) ? 2 : 0);
485 const int nScore = cur_arrival[j].score + 1;
486 const int nRepOffset = cur_arrival[j].rep_offset;
487
488 if (nCodingChoiceCost < pDestLiteralSlots[nArrivalsPerPosition - 1].cost ||
489 (nCodingChoiceCost == pDestLiteralSlots[nArrivalsPerPosition - 1].cost &&
490 nScore < pDestLiteralSlots[nArrivalsPerPosition - 1].score &&
491 nRepOffset != pDestLiteralSlots[nArrivalsPerPosition - 1].rep_offset)) {
492 int exists = 0, n;
493
494 for (n = 0;
495 pDestLiteralSlots[n].cost < nCodingChoiceCost;
496 n++) {
497 if (pDestLiteralSlots[n].rep_offset == nRepOffset) {
498 exists = 1;
499 break;
500 }
501 }
502
503 if (!exists) {
504 for (;
505 pDestLiteralSlots[n].cost == nCodingChoiceCost && nScore >= pDestLiteralSlots[n].score;
506 n++) {
507 if (pDestLiteralSlots[n].rep_offset == nRepOffset) {
508 exists = 1;
509 break;
510 }
511 }
512
513 if (!exists) {
514 int z;
515
516 for (z = n; z < nArrivalsPerPosition - 1 && pDestLiteralSlots[z].cost == nCodingChoiceCost; z++) {
517 if (pDestLiteralSlots[z].rep_offset == nRepOffset) {
518 exists = 1;
519 break;
520 }
521 }
522
523 if (!exists) {
524 for (; z < nArrivalsPerPosition - 1 && pDestLiteralSlots[z].from_slot; z++) {
525 if (pDestLiteralSlots[z].rep_offset == nRepOffset)
526 break;
527 }
528
529 memmove(&pDestLiteralSlots[n + 1],
530 &pDestLiteralSlots[n],
531 sizeof(salvador_arrival) * (z - n));
532
533 salvador_arrival* pDestArrival = &pDestLiteralSlots[n];
534 pDestArrival->cost = nCodingChoiceCost;
535 pDestArrival->from_pos = i;
536 pDestArrival->from_slot = j + 1;
537 pDestArrival->rep_offset = nRepOffset;
538 pDestArrival->rep_pos = cur_arrival[j].rep_pos;
539 pDestArrival->match_len = 0;
540 pDestArrival->num_literals = nNumLiterals;
541 pDestArrival->score = nScore;
542 }
543 }
544 }
545 }
546 }
547
548 if (i == nStartOffset && (nBlockFlags & 1)) continue;
549
550 const int nNumArrivalsForThisPos = j;
551 int nOverallMinRepLen = 0, nOverallMaxRepLen = 0;
552
553 int nRepMatchArrivalIdx[(2 * NMAX_ARRIVALS_PER_POSITION) + 1];
554 int nNumRepMatchArrivals = 0;
555
556 if (i < nEndOffset) {
557 unsigned int nMaxRepLenForPos = nEndOffset - i;
558 if (nMaxRepLenForPos > LCP_MAX)
559 nMaxRepLenForPos = LCP_MAX;
560
561 const unsigned char* pInWindowStart = pInWindow + i;
562 const unsigned char* pInWindowMax = pInWindowStart + nMaxRepLenForPos;
563
564 for (j = 0; j < nNumArrivalsForThisPos; j++) {
565 if (cur_arrival[j].num_literals) {
566 const int nRepOffset = cur_arrival[j].rep_offset;
567
568 if (i >= nRepOffset) {
569 if (pInWindowStart[0] == pInWindowStart[-nRepOffset]) {
570 if (nRepOffset) {
571 const int nLen0 = rle_len[i - nRepOffset];
572 const int nLen1 = rle_len[i];
573 const int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1;
574 const unsigned char* pInWindowAtPos = pInWindowStart + nMinLen;
575
576 if (pInWindowAtPos > pInWindowMax)
577 pInWindowAtPos = pInWindowMax;
578
579 while ((pInWindowAtPos + 8) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nRepOffset, 8))
580 pInWindowAtPos += 8;
581 while ((pInWindowAtPos + 4) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nRepOffset, 4))
582 pInWindowAtPos += 4;
583 while (pInWindowAtPos < pInWindowMax && pInWindowAtPos[0] == pInWindowAtPos[-nRepOffset])
584 pInWindowAtPos++;
585 const int nCurRepLen = (const int)(pInWindowAtPos - pInWindowStart);
586
587 if (nOverallMaxRepLen < nCurRepLen)
588 nOverallMaxRepLen = nCurRepLen;
589 nRepMatchArrivalIdx[nNumRepMatchArrivals++] = j;
590 nRepMatchArrivalIdx[nNumRepMatchArrivals++] = nCurRepLen;
591 }
592 }
593 }
594 }
595 }
596 }
597 nRepMatchArrivalIdx[nNumRepMatchArrivals] = -1;
598
599 const salvador_match* match = pCompressor->match + ((i - nStartOffset) * NMATCHES_PER_INDEX);
600 const unsigned short* match_depth = pCompressor->match_depth + ((i - nStartOffset) * NMATCHES_PER_INDEX);
601
602 for (m = 0; m < NMATCHES_PER_INDEX && match[m].length; m++) {
603 int nOrigMatchLen = match[m].length;
604 const int nOrigMatchOffset = match[m].offset;
605 const unsigned int nOrigMatchDepth = match_depth[m];
606 unsigned int d;
607
608 if ((i + nOrigMatchLen) > nEndOffset)
609 nOrigMatchLen = nEndOffset - i;
610
611 for (d = 0; d <= nOrigMatchDepth; d += (nOrigMatchDepth ? nOrigMatchDepth : 1)) {
612 const int nMatchLen = nOrigMatchLen - d;
613 const int nMatchOffset = nOrigMatchOffset - d;
614 int nNonRepMatchArrivalIdx, nStartingMatchLen, k;
615
616 if (nInsertForwardReps) {
617 salvador_insert_forward_match(pCompressor, pInWindow, i, nMatchOffset, nStartOffset, nEndOffset, 0);
618 }
619
620 nNonRepMatchArrivalIdx = -1;
621 for (j = 0; j < nNumArrivalsForThisPos; j++) {
622 const int nRepOffset = cur_arrival[j].rep_offset;
623
624 if (nMatchOffset != nRepOffset || cur_arrival[j].num_literals == 0) {
625 nNonRepMatchArrivalIdx = j;
626 break;
627 }
628 }
629
630 if (nNonRepMatchArrivalIdx >= 0) {
631 const int nNoRepmatchOffsetCost = cur_arrival[nNonRepMatchArrivalIdx].cost /* the actual cost of the literals themselves accumulates up the chain */ + OFFSET_COST(nMatchOffset);
632 const int nNoRepmatchScore = cur_arrival[nNonRepMatchArrivalIdx].score + 3;
633
634 /* Insert non-repmatch candidate */
635
636 if (nMatchLen < LEAVE_ALONE_MATCH_SIZE) {
637 nStartingMatchLen = 2;
638 }
639 else {
640 nStartingMatchLen = nMatchLen;
641 }
642
643 for (k = nStartingMatchLen; k <= nMatchLen; k++) {
644 salvador_arrival* pDestSlots = &cur_arrival[k * nMaxArrivalsPerPosition];
645 const int nMatchLenCost = (k < 8192) ? salvador_cost_for_len[k - 1] : (salvador_get_match_varlen_size_norep(k) + TOKEN_SIZE /* token */);
646 const int nCodingChoiceCost = nMatchLenCost + nNoRepmatchOffsetCost;
647
648 if (nCodingChoiceCost < pDestSlots[nArrivalsPerPosition - 2].cost ||
649 (nCodingChoiceCost == pDestSlots[nArrivalsPerPosition - 2].cost &&
650 nNoRepmatchScore < pDestSlots[nArrivalsPerPosition - 2].score &&
651 (nCodingChoiceCost != pDestSlots[nArrivalsPerPosition - 1].cost || nMatchOffset != pDestSlots[nArrivalsPerPosition - 1].rep_offset))) {
652 int exists = 0, n;
653
654 for (n = 0;
655 pDestSlots[n].cost < nCodingChoiceCost;
656 n++) {
657 if (pDestSlots[n].rep_offset == nMatchOffset) {
658 exists = 1;
659 break;
660 }
661 }
662
663 if (!exists) {
664 for (;
665 pDestSlots[n].cost == nCodingChoiceCost && nNoRepmatchScore >= pDestSlots[n].score;
666 n++) {
667 if (pDestSlots[n].rep_offset == nMatchOffset) {
668 exists = 1;
669 break;
670 }
671 }
672
673 if (!exists) {
674 int z;
675
676 for (z = n; z < nArrivalsPerPosition - 1 && pDestSlots[z].cost == nCodingChoiceCost; z++) {
677 if (pDestSlots[z].rep_offset == nMatchOffset) {
678 exists = 1;
679 break;
680 }
681 }
682
683 if (!exists) {
684 for (; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) {
685 if (pDestSlots[z].rep_offset == nMatchOffset)
686 break;
687 }
688
689 memmove(&pDestSlots[n + 1],
690 &pDestSlots[n],
691 sizeof(salvador_arrival) * (z - n));
692
693 salvador_arrival* pDestArrival = &pDestSlots[n];
694 pDestArrival->cost = nCodingChoiceCost;
695 pDestArrival->from_pos = i;
696 pDestArrival->from_slot = nNonRepMatchArrivalIdx + 1;
697 pDestArrival->rep_offset = nMatchOffset;
698 pDestArrival->rep_pos = i;
699 pDestArrival->match_len = k;
700 pDestArrival->num_literals = 0;
701 pDestArrival->score = nNoRepmatchScore;
702 }
703 }
704 }
705 }
706 }
707 }
708
709 /* Insert repmatch candidates */
710
711 if (nMatchLen < LEAVE_ALONE_MATCH_SIZE || nMatchLen <= nOverallMinRepLen) {
712 nStartingMatchLen = nOverallMinRepLen + 1;
713 }
714 else {
715 nStartingMatchLen = nMatchLen;
716 }
717
718 for (k = nStartingMatchLen; k <= (nOverallMaxRepLen < nMatchLen ? nOverallMaxRepLen : nMatchLen); k++) {
719 const int nMatchLenCost = (k < 8192) ? salvador_cost_for_len[k] : (salvador_get_match_varlen_size_rep(k) + TOKEN_SIZE /* token */);
720 salvador_arrival* pDestSlots = &cur_arrival[k * nMaxArrivalsPerPosition];
721 int nCurRepMatchArrival;
722
723 for (nCurRepMatchArrival = 0; (j = nRepMatchArrivalIdx[nCurRepMatchArrival]) >= 0; nCurRepMatchArrival += 2) {
724 if (nRepMatchArrivalIdx[nCurRepMatchArrival + 1] >= k) {
725 const int nRepCodingChoiceCost = cur_arrival[j].cost /* the actual cost of the literals themselves accumulates up the chain */ + nMatchLenCost;
726 const int nScore = cur_arrival[j].score + 2;
727 const int nRepOffset = cur_arrival[j].rep_offset;
728
729 if (nRepCodingChoiceCost < pDestSlots[nArrivalsPerPosition - 1].cost ||
730 (nRepCodingChoiceCost == pDestSlots[nArrivalsPerPosition - 1].cost &&
731 nScore < pDestSlots[nArrivalsPerPosition - 1].score &&
732 nRepOffset != pDestSlots[nArrivalsPerPosition - 1].rep_offset)) {
733 int exists = 0, n;
734
735 for (n = 0;
736 pDestSlots[n].cost < nRepCodingChoiceCost;
737 n++) {
738 if (pDestSlots[n].rep_offset == nRepOffset) {
739 exists = 1;
740 break;
741 }
742 }
743
744 if (!exists) {
745 for (;
746 pDestSlots[n].cost == nRepCodingChoiceCost && nScore >= pDestSlots[n].score;
747 n++) {
748 if (pDestSlots[n].rep_offset == nRepOffset) {
749 exists = 1;
750 break;
751 }
752 }
753
754 if (!exists) {
755 int z;
756
757 for (z = n; z < nArrivalsPerPosition - 1 && pDestSlots[z].cost == nRepCodingChoiceCost; z++) {
758 if (pDestSlots[z].rep_offset == nRepOffset) {
759 exists = 1;
760 break;
761 }
762 }
763
764 if (!exists) {
765 for (; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) {
766 if (pDestSlots[z].rep_offset == nRepOffset)
767 break;
768 }
769
770 memmove(&pDestSlots[n + 1],
771 &pDestSlots[n],
772 sizeof(salvador_arrival) * (z - n));
773
774 salvador_arrival* pDestArrival = &pDestSlots[n];
775 pDestArrival->cost = nRepCodingChoiceCost;
776 pDestArrival->from_pos = i;
777 pDestArrival->from_slot = j + 1;
778 pDestArrival->rep_offset = nRepOffset;
779 pDestArrival->rep_pos = i;
780 pDestArrival->match_len = k;
781 pDestArrival->num_literals = 0;
782 pDestArrival->score = nScore;
783 }
784 }
785 }
786 }
787 else {
788 break;
789 }
790 }
791 }
792
793 if (k <= LEAVE_ALONE_MATCH_SIZE)
794 nOverallMinRepLen = k;
795 else if (nOverallMaxRepLen == k)
796 nOverallMaxRepLen--;
797 }
798 }
799
800 if (nOrigMatchLen >= 1280 && ((m + 1) >= NMATCHES_PER_INDEX || match[m + 1].length < 512))
801 break;
802 }
803 }
804
805 if (!nInsertForwardReps) {
806 const salvador_arrival* end_arrival = &arrival[i * nMaxArrivalsPerPosition];
807 salvador_match* pBestMatch = pCompressor->best_match - nStartOffset;
808
809 while (end_arrival->from_slot > 0 && end_arrival->from_pos < (const unsigned int)nEndOffset) {
810 pBestMatch[end_arrival->from_pos].length = end_arrival->match_len;
811 pBestMatch[end_arrival->from_pos].offset = (end_arrival->match_len) ? end_arrival->rep_offset : 0;
812
813 end_arrival = &arrival[(end_arrival->from_pos * nMaxArrivalsPerPosition) + (end_arrival->from_slot - 1)];
814 }
815 }
816 }
817
818 /**
819 * Attempt to replace matches by literals when it makes the final bitstream smaller, and merge large matches
820 *
821 * @param pCompressor compression context
822 * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress)
823 * @param nStartOffset current offset in input window (typically the number of previously compressed bytes)
824 * @param nEndOffset offset to end finding matches at (typically the size of the total input window in bytes
825 * @param nCurRepMatchOffset starting rep offset for this block
826 * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise
827 *
828 * @return non-zero if the number of tokens was reduced, 0 if it wasn't
829 */
830 static int salvador_reduce_commands(salvador_compressor *pCompressor, const unsigned char *pInWindow, const int nStartOffset, const int nEndOffset, const int *nCurRepMatchOffset, const int nBlockFlags) {
831 salvador_match* pBestMatch = pCompressor->best_match - nStartOffset;
832 int i;
833 int nNumLiterals = nBlockFlags & 1;
834 int nRepMatchOffset = *nCurRepMatchOffset;
835 int nDidReduce = 0;
836
837 for (i = nStartOffset + (nBlockFlags & 1); i < nEndOffset; ) {
838 salvador_match *pMatch = pBestMatch + i;
839
840 if (pMatch->length == 0 &&
841 (i + 1) < nEndOffset &&
842 pBestMatch[i + 1].length >= MIN_ENCODED_MATCH_SIZE &&
843 pBestMatch[i + 1].length < MAX_VARLEN &&
844 pBestMatch[i + 1].offset &&
845 i >= pBestMatch[i + 1].offset &&
846 (i + pBestMatch[i + 1].length + 1) <= nEndOffset &&
847 (nNumLiterals != 0 || pBestMatch[i + 1].offset != nRepMatchOffset) &&
848 !memcmp(pInWindow + i - (pBestMatch[i + 1].offset), pInWindow + i, pBestMatch[i + 1].length + 1)) {
849 int nCurLenSize, nReducedLenSize;
850
851 if (pBestMatch[i + 1].offset == nRepMatchOffset) {
852 nCurLenSize = salvador_get_literals_varlen_size(nNumLiterals + 1) + 8 + salvador_get_match_varlen_size_rep(pBestMatch[i + 1].length);
853 }
854 else {
855 nCurLenSize = salvador_get_literals_varlen_size(nNumLiterals + 1) + 8 +
856 salvador_get_elias_size(((pBestMatch[i + 1].offset - 1) >> 7) + 1) + 7 +
857 salvador_get_match_varlen_size_norep(pBestMatch[i + 1].length);
858 }
859
860 if (nNumLiterals != 0 && pBestMatch[i + 1].offset == nRepMatchOffset && nRepMatchOffset) {
861 nReducedLenSize = salvador_get_literals_varlen_size(nNumLiterals) + salvador_get_match_varlen_size_rep(pBestMatch[i + 1].length + 1);
862 }
863 else {
864 nReducedLenSize = salvador_get_literals_varlen_size(nNumLiterals) +
865 salvador_get_elias_size(((pBestMatch[i + 1].offset - 1) >> 7) + 1) + 7 +
866 salvador_get_match_varlen_size_norep(pBestMatch[i + 1].length + 1);
867 }
868
869 if (nReducedLenSize <= nCurLenSize) {
870 /* Merge */
871 pBestMatch[i].length = pBestMatch[i + 1].length + 1;
872 pBestMatch[i].offset = pBestMatch[i + 1].offset;
873 pBestMatch[i + 1].length = 0;
874 pBestMatch[i + 1].offset = 0;
875 nDidReduce = 1;
876 continue;
877 }
878 }
879
880 if (pMatch->length >= MIN_ENCODED_MATCH_SIZE) {
881 if ((i + pMatch->length) < nEndOffset /* Don't consider the last match in the block, we can only reduce a match inbetween other tokens */) {
882 int nNextIndex = i + pMatch->length;
883 int nNextLiterals = 0;
884
885 while (nNextIndex < nEndOffset && pBestMatch[nNextIndex].length == 0) {
886 nNextLiterals++;
887 nNextIndex++;
888 }
889
890 if (nNextIndex < nEndOffset) {
891 /* This command is a match, is followed by 'nNextLiterals' literals and then by another match */
892
893 if (pBestMatch[nNextIndex].length >= MIN_ENCODED_MATCH_SIZE) {
894 if (nNumLiterals != 0 && nRepMatchOffset && pMatch->offset != nRepMatchOffset && (pBestMatch[nNextIndex].offset != pMatch->offset ||
895 OFFSET_COST(pMatch->offset) > OFFSET_COST(pBestMatch[nNextIndex].offset))) {
896 /* Check if we can get a missed backward repmatch */
897 if (i >= nRepMatchOffset &&
898 (i - nRepMatchOffset + pMatch->length) <= nEndOffset) {
899 int nMaxLen = 0;
900 while ((nMaxLen + 8) < pMatch->length && !memcmp(pInWindow + i - nRepMatchOffset + nMaxLen, pInWindow + i - pMatch->offset + nMaxLen, 8))
901 nMaxLen += 8;
902 while ((nMaxLen + 4) < pMatch->length && !memcmp(pInWindow + i - nRepMatchOffset + nMaxLen, pInWindow + i - pMatch->offset + nMaxLen, 4))
903 nMaxLen += 4;
904 while (nMaxLen < pMatch->length && pInWindow[i - nRepMatchOffset + nMaxLen] == pInWindow[i - pMatch->offset + nMaxLen])
905 nMaxLen++;
906
907 if (nMaxLen >= 1) {
908 int nCurCommandSize, nReducedCommandSize;
909
910 /* -- Original: Match with offset. Skip 'match with offset follows' bit. -- */
911
912 /* High bits of match offset */
913 nCurCommandSize = salvador_get_elias_size(((pMatch->offset - 1) >> 7) + 1);
914
915 /* Low byte of match offset */
916 nCurCommandSize += 7;
917
918 /* Match length */
919 nCurCommandSize += salvador_get_match_varlen_size_norep(pMatch->length);
920
921 /* Literals after command */
922 nCurCommandSize += salvador_get_literals_varlen_size(nNextLiterals);
923
924 /* -- Reduced: Rep match. Skip 'rep-match follows' bit. -- */
925
926 /* Match length */
927 nReducedCommandSize = salvador_get_match_varlen_size_rep(nMaxLen);
928
929 /* Literals after command */
930 nReducedCommandSize += (pMatch->length - nMaxLen) << 3;
931 nReducedCommandSize += salvador_get_literals_varlen_size(nNextLiterals + (pMatch->length - nMaxLen));
932
933 if (nReducedCommandSize < nCurCommandSize) {
934 int j;
935
936 /* Change to repmatch */
937
938 pMatch->offset = nRepMatchOffset;
939 for (j = nMaxLen; j < pMatch->length; j++) {
940 pBestMatch[i + j].length = 0;
941 }
942 pMatch->length = nMaxLen;
943 nDidReduce = 1;
944 }
945 }
946 }
947 }
948
949 if (pBestMatch[nNextIndex].offset && pMatch->offset != pBestMatch[nNextIndex].offset && nRepMatchOffset != pBestMatch[nNextIndex].offset && nNextLiterals) {
950 /* Otherwise, try to gain a match forward as well */
951 if (i >= pBestMatch[nNextIndex].offset && (i - pBestMatch[nNextIndex].offset + pMatch->length) <= nEndOffset && pMatch->offset != nRepMatchOffset) {
952 int nMaxLen = 0;
953 while ((nMaxLen + 8) < pMatch->length && !memcmp(pInWindow + i - pBestMatch[nNextIndex].offset + nMaxLen, pInWindow + i - pMatch->offset + nMaxLen, 8))
954 nMaxLen += 8;
955 while ((nMaxLen + 4) < pMatch->length && !memcmp(pInWindow + i - pBestMatch[nNextIndex].offset + nMaxLen, pInWindow + i - pMatch->offset + nMaxLen, 4))
956 nMaxLen += 4;
957 while (nMaxLen < pMatch->length && pInWindow[i - pBestMatch[nNextIndex].offset + nMaxLen] == pInWindow[i - pMatch->offset + nMaxLen])
958 nMaxLen++;
959 if (nMaxLen >= pMatch->length) {
960 /* Replace */
961 pMatch->offset = pBestMatch[nNextIndex].offset;
962 nDidReduce = 1;
963 }
964 else if (nMaxLen >= 2) {
965 int nPartialSizeBefore, nPartialSizeAfter;
966
967 nPartialSizeBefore = salvador_get_match_varlen_size_norep(pMatch->length);
968 nPartialSizeBefore += OFFSET_COST(pMatch->offset);
969 nPartialSizeBefore += salvador_get_literals_varlen_size(nNextLiterals);
970
971 nPartialSizeAfter = salvador_get_match_varlen_size_rep(nMaxLen);
972 nPartialSizeAfter += salvador_get_literals_varlen_size(nNextLiterals + (pMatch->length - nMaxLen)) + ((pMatch->length - nMaxLen) << 3);
973
974 if (nPartialSizeAfter < nPartialSizeBefore) {
975 int j;
976
977 /* We gain a repmatch that is shorter than the original match as this is the best we can do, so it is followed by extra literals, but
978 * we have calculated that this is shorter */
979 pMatch->offset = pBestMatch[nNextIndex].offset;
980 for (j = nMaxLen; j < pMatch->length; j++) {
981 pBestMatch[i + j].length = 0;
982 }
983 pMatch->length = nMaxLen;
984 nDidReduce = 1;
985 }
986 }
987 }
988 }
989 }
990
991 if (pMatch->length < 9 /* Don't waste time considering large matches, they will always win over literals */) {
992 /* Calculate this command's current cost */
993
994 int nCurCommandSize = salvador_get_literals_varlen_size(nNumLiterals);
995 /* Don't include current command's literal databits */
996
997 if (pMatch->offset == nRepMatchOffset && nNumLiterals != 0 && nRepMatchOffset) {
998 /* Rep match - don't include 'rep match follows' bit */
999
1000 /* Match length */
1001 nCurCommandSize += salvador_get_match_varlen_size_rep(pMatch->length);
1002 }
1003 else {
1004 /* Match with offset - don't include 'match with offset follows' bit */
1005
1006 /* High bits of match offset */
1007 nCurCommandSize += salvador_get_elias_size(((pMatch->offset - 1) >> 7) + 1);
1008
1009 /* Low byte of match offset */
1010 nCurCommandSize += 7;
1011
1012 /* Match length */
1013 nCurCommandSize += salvador_get_match_varlen_size_norep(pMatch->length);
1014 }
1015
1016 /* Calculate the next command's current cost */
1017 int nNextCommandSize = salvador_get_literals_varlen_size(nNextLiterals);
1018 /* Don't include next command's literal databits */
1019
1020 /* Rep match or match with offset follows */
1021 nNextCommandSize += 1;
1022
1023 if (pMatch->offset && pBestMatch[nNextIndex].offset == pMatch->offset && nNextLiterals != 0) {
1024 /* Match length */
1025 nNextCommandSize += salvador_get_match_varlen_size_rep(pBestMatch[nNextIndex].length);
1026 }
1027 else {
1028 /* High bits of match offset */
1029 nNextCommandSize += salvador_get_elias_size(((pBestMatch[nNextIndex].offset - 1) >> 7) + 1);
1030
1031 /* Low byte of match offset */
1032 nNextCommandSize += 7;
1033
1034 /* Match length */
1035 nNextCommandSize += salvador_get_match_varlen_size_norep(pBestMatch[nNextIndex].length);
1036 }
1037
1038 const int nOriginalCombinedCommandSize = nCurCommandSize + nNextCommandSize;
1039
1040 /* Calculate the cost of replacing this match command by literals + the next command with the cost of encoding these literals */
1041 int nReducedCommandSize = (pMatch->length << 3);
1042 nReducedCommandSize += salvador_get_literals_varlen_size(nNumLiterals + pMatch->length + nNextLiterals);
1043 /* Don't include current + next command's literal databits */
1044
1045 if (pBestMatch[nNextIndex].offset == nRepMatchOffset && (nNumLiterals + pMatch->length + nNextLiterals) != 0 && nRepMatchOffset) {
1046 /* Rep match - don't include 'rep match follows' bit */
1047
1048 /* Match length */
1049 nReducedCommandSize += salvador_get_match_varlen_size_rep(pBestMatch[nNextIndex].length);
1050 }
1051 else {
1052 /* Match with offset - don't include 'match with offset follows' bit */
1053
1054 /* High bits of match offset */
1055 nReducedCommandSize += salvador_get_elias_size(((pBestMatch[nNextIndex].offset - 1) >> 7) + 1);
1056
1057 /* Low byte of match offset */
1058 nReducedCommandSize += 7;
1059
1060 /* Match length */
1061 nReducedCommandSize += salvador_get_match_varlen_size_norep(pBestMatch[nNextIndex].length);
1062 }
1063
1064 if (nOriginalCombinedCommandSize >= nReducedCommandSize) {
1065 /* Reduce */
1066 const int nMatchLen = pMatch->length;
1067 int j;
1068
1069 for (j = 0; j < nMatchLen; j++) {
1070 pBestMatch[i + j].length = 0;
1071 }
1072
1073 nDidReduce = 1;
1074 continue;
1075 }
1076 }
1077 }
1078 }
1079
1080 if ((i + pMatch->length) < nEndOffset && pMatch->offset && pMatch->length >= MIN_ENCODED_MATCH_SIZE &&
1081 pBestMatch[i + pMatch->length].offset &&
1082 pBestMatch[i + pMatch->length].length >= MIN_ENCODED_MATCH_SIZE &&
1083 (pMatch->length + pBestMatch[i + pMatch->length].length) <= MAX_VARLEN &&
1084 (i + pMatch->length) >= pMatch->offset &&
1085 (i + pMatch->length) >= pBestMatch[i + pMatch->length].offset &&
1086 (i + pMatch->length + pBestMatch[i + pMatch->length].length) <= nEndOffset &&
1087 !memcmp(pInWindow + i - pMatch->offset + pMatch->length,
1088 pInWindow + i + pMatch->length - pBestMatch[i + pMatch->length].offset,
1089 pBestMatch[i + pMatch->length].length)) {
1090
1091 int nNextIndex = i + pMatch->length + pBestMatch[i + pMatch->length].length;
1092 int nNextLiterals = 0;
1093
1094 while (nNextIndex < nEndOffset && pBestMatch[nNextIndex].length == 0) {
1095 nNextIndex++;
1096 nNextLiterals++;
1097 }
1098
1099 int nCurPartialSize;
1100 if (pMatch->offset == nRepMatchOffset && nNumLiterals != 0) {
1101 /* Rep match. Don't include 'rep-match follows' bit. */
1102
1103 /* Match length */
1104 nCurPartialSize = salvador_get_match_varlen_size_rep(pMatch->length);
1105 }
1106 else {
1107 /* Match with offset. Don't include 'match with offset follows' bit. */
1108
1109 /* High bits of match offset */
1110 nCurPartialSize = salvador_get_elias_size(((pMatch->offset - 1) >> 7) + 1);
1111
1112 /* Low byte of match offset */
1113 nCurPartialSize += 7;
1114
1115 /* Match length */
1116 nCurPartialSize += salvador_get_match_varlen_size_norep(pMatch->length);
1117 }
1118
1119 /* Match with offset */
1120 nCurPartialSize += 1; /* match with offset */
1121
1122 /* High bits of match offset */
1123 nCurPartialSize += salvador_get_elias_size(((pBestMatch[i + pMatch->length].offset - 1) >> 7) + 1);
1124
1125 /* Low byte of match offset */
1126 nCurPartialSize += 7;
1127
1128 /* Match length */
1129 nCurPartialSize += salvador_get_match_varlen_size_norep(pBestMatch[i + pMatch->length].length);
1130
1131 if (nNextIndex < nEndOffset) {
1132 if (pBestMatch[i + pMatch->length].offset && pBestMatch[nNextIndex].offset == pBestMatch[i + pMatch->length].offset && nNextLiterals != 0) {
1133 /* Rep match. Don't include 'rep-match follows' bit. */
1134
1135 /* Match length */
1136 nCurPartialSize += salvador_get_match_varlen_size_rep(pBestMatch[nNextIndex].length);
1137 }
1138 else {
1139 /* Match with offset. Don't include 'match with offset follows' bit. */
1140
1141 /* High bits of match offset */
1142 nCurPartialSize += salvador_get_elias_size(((pBestMatch[nNextIndex].offset - 1) >> 7) + 1);
1143
1144 /* Low byte of match offset */
1145 nCurPartialSize += 7;
1146
1147 /* Match length */
1148 nCurPartialSize += salvador_get_match_varlen_size_norep(pBestMatch[nNextIndex].length);
1149 }
1150 }
1151
1152 int nReducedPartialSize;
1153 if (pMatch->offset == nRepMatchOffset && nNumLiterals != 0 && nRepMatchOffset) {
1154 /* Rep match. Don't include 'rep-match follows' bit. */
1155
1156 /* Match length */
1157 nReducedPartialSize = salvador_get_match_varlen_size_rep(pMatch->length + pBestMatch[i + pMatch->length].length);
1158 }
1159 else {
1160 /* Match with offset. Don't include 'match with offset follows' bit. */
1161
1162 /* High bits of match offset */
1163 nReducedPartialSize = salvador_get_elias_size(((pMatch->offset - 1) >> 7) + 1);
1164
1165 /* Low byte of match offset */
1166 nReducedPartialSize += 7;
1167
1168 /* Match length */
1169 nReducedPartialSize += salvador_get_match_varlen_size_norep(pMatch->length + pBestMatch[i + pMatch->length].length);
1170 }
1171
1172 int nCannotReduce = 0;
1173 if (nNextIndex < nEndOffset) {
1174 if (pMatch->offset && pBestMatch[nNextIndex].offset == pMatch->offset && nNextLiterals != 0) {
1175 /* Rep match. Don't include 'rep-match follows' bit. */
1176
1177 /* Match length */
1178 nReducedPartialSize += salvador_get_match_varlen_size_rep(pBestMatch[nNextIndex].length);
1179 }
1180 else {
1181 if (pBestMatch[nNextIndex].length >= MIN_ENCODED_MATCH_SIZE) {
1182 /* Match with offset. Don't include 'match with offset follows' bit. */
1183
1184 /* High bits of match offset */
1185 nReducedPartialSize += salvador_get_elias_size(((pBestMatch[nNextIndex].offset - 1) >> 7) + 1);
1186
1187 /* Low byte of match offset */
1188 nReducedPartialSize += 7;
1189
1190 /* Match length */
1191 nReducedPartialSize += salvador_get_match_varlen_size_norep(pBestMatch[nNextIndex].length);
1192 }
1193 else {
1194 nCannotReduce = 1;
1195 }
1196 }
1197 }
1198
1199 if (nCurPartialSize >= nReducedPartialSize && !nCannotReduce) {
1200 const int nMatchLen = pMatch->length;
1201
1202 /* Join */
1203
1204 pMatch->length += pBestMatch[i + nMatchLen].length;
1205 pBestMatch[i + nMatchLen].length = 0;
1206 pBestMatch[i + nMatchLen].offset = 0;
1207 nDidReduce = 1;
1208 continue;
1209 }
1210 }
1211
1212 if (nNumLiterals != 0 && pMatch->offset != nRepMatchOffset && pMatch->length == MIN_ENCODED_MATCH_SIZE && nRepMatchOffset) {
1213 if ((i + MIN_ENCODED_MATCH_SIZE /* pMatch->length */) < nEndOffset) {
1214 int nNextIndex = i + MIN_ENCODED_MATCH_SIZE /* pMatch->length */;
1215 int nNextLiterals = 0;
1216
1217 /* Check if we can turn a match + a 1 byte rep match into all literals, and either reduce the output or keep it the same size */
1218
1219 while (nNextIndex < nEndOffset && pBestMatch[nNextIndex].length == 0) {
1220 nNextLiterals++;
1221 nNextIndex++;
1222 }
1223
1224 if (nNextIndex < nEndOffset && nNextLiterals != 0 &&
1225 pBestMatch[nNextIndex].length == 1 &&
1226 pBestMatch[nNextIndex].offset == pMatch->offset) {
1227 int nNextNextIndex = nNextIndex + 1 /* pBestMatch[nNextIndex].length */;
1228 int nNextNextLiterals = 0;
1229
1230 while (nNextNextIndex < nEndOffset && pBestMatch[nNextNextIndex].length == 0) {
1231 nNextNextLiterals++;
1232 nNextNextIndex++;
1233 }
1234
1235 if (nNextNextIndex < nEndOffset && nNextNextLiterals != 0 &&
1236 pBestMatch[nNextNextIndex].length >= MIN_ENCODED_MATCH_SIZE &&
1237 pBestMatch[nNextNextIndex].offset != pBestMatch[nNextIndex].offset) {
1238 int nCurCommandSize, nCurRepMatchSize, nReducedCommandSize;
1239
1240 /* First command: match with offset */
1241 nCurCommandSize = salvador_get_literals_varlen_size(nNumLiterals);
1242 /* Don't include match with offset's literal databits */
1243
1244 /* Match with offset */
1245 nCurCommandSize += 1; /* match with offset follows */
1246
1247 /* High bits of match offset */
1248 nCurCommandSize += salvador_get_elias_size(((pMatch->offset - 1) >> 7) + 1);
1249
1250 /* Low byte of match offset */
1251 nCurCommandSize += 7;
1252
1253 /* Match length */
1254 nCurCommandSize += 1 /* salvador_get_match_varlen_size_norep(pMatch->length) */;
1255
1256 /* Second command: rep-match */
1257 nCurRepMatchSize = salvador_get_literals_varlen_size(nNextLiterals);
1258 nCurRepMatchSize += (nNextLiterals << 3);
1259
1260 nCurRepMatchSize += 1; /* rep-match follows */
1261 nCurRepMatchSize += 1 /* salvador_get_match_varlen_size_rep(pBestMatch[nNextIndex].length) */;
1262
1263 /* Combined commands as literals */
1264 nReducedCommandSize = salvador_get_literals_varlen_size(nNumLiterals + MIN_ENCODED_MATCH_SIZE /* pMatch->length */ + nNextLiterals + 1 /* pBestMatch[nNextIndex].length */);
1265 /* Don't include combined command's literal databits */
1266 nReducedCommandSize += (MIN_ENCODED_MATCH_SIZE /* pMatch->length */ << 3);
1267 nReducedCommandSize += (nNextLiterals << 3);
1268 nReducedCommandSize += (1 /* pBestMatch[nNextIndex].length */ << 3);
1269
1270 if ((nCurCommandSize + nCurRepMatchSize) >= nReducedCommandSize) {
1271 int j;
1272
1273 for (j = 0; j < MIN_ENCODED_MATCH_SIZE /* pMatch->length */; j++) {
1274 pBestMatch[i + j].length = 0;
1275 }
1276
1277 pBestMatch[nNextIndex].length = 0;
1278 nDidReduce = 1;
1279 }
1280 }
1281 }
1282 }
1283 }
1284
1285 nRepMatchOffset = pMatch->offset;
1286
1287 i += pMatch->length;
1288 nNumLiterals = 0;
1289 }
1290 else if (pMatch->length == 1) {
1291 if (nNumLiterals != 0) {
1292 int nNextIndex = i + 1 /* pMatch->length */;
1293 int nNextLiterals = 0;
1294
1295 while (nNextIndex < nEndOffset && pBestMatch[nNextIndex].length == 0) {
1296 nNextLiterals++;
1297 nNextIndex++;
1298 }
1299
1300 if (nRepMatchOffset != pMatch->offset && (nNextIndex < nEndOffset || !nDidReduce)) {
1301 pMatch->length = 0;
1302 pMatch->offset = 0;
1303 nDidReduce = 1;
1304 continue;
1305 }
1306
1307 if (nNextLiterals != 0) {
1308 int nCurPartialSize = salvador_get_literals_varlen_size(nNumLiterals);
1309 nCurPartialSize += TOKEN_SIZE + 1 /* salvador_get_match_varlen_size_rep(pMatch->length) */;
1310 nCurPartialSize += salvador_get_literals_varlen_size(nNextLiterals);
1311
1312 const int nReducedPartialSize = salvador_get_literals_varlen_size(nNumLiterals + 1 + nNextLiterals) + 8;
1313
1314 if (nCurPartialSize >= nReducedPartialSize) {
1315 pMatch->length = 0;
1316 pMatch->offset = 0;
1317 nDidReduce = 1;
1318 continue;
1319 }
1320 }
1321 }
1322
1323 nNumLiterals = 0;
1324 i++;
1325 }
1326 else {
1327 nNumLiterals++;
1328 i++;
1329 }
1330 }
1331
1332 return nDidReduce;
1333 }
1334
1335 /**
1336 * Emit a block of compressed data
1337 *
1338 * @param pCompressor compression context
1339 * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress)
1340 * @param nStartOffset current offset in input window (typically the number of previously compressed bytes)
1341 * @param nEndOffset offset to end finding matches at (typically the size of the total input window in bytes
1342 * @param pOutData pointer to output buffer
1343 * @param nMaxOutDataSize maximum size of output buffer, in bytes
1344 * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits
1345 * @param nCurBitShift bit shift count
1346 * @param nFinalLiterals output number of literals not written after writing this block, that need to be written in the next block
1347 * @param nCurRepMatchOffset starting rep offset for this block, updated after the block is compressed successfully
1348 * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise
1349 *
1350 * @return size of compressed data in output buffer, or -1 if the data is uncompressible
1351 */
1352 static int salvador_write_block(salvador_compressor* pCompressor, const unsigned char* pInWindow, const int nStartOffset, const int nEndOffset, unsigned char* pOutData, const int nMaxOutDataSize, int* nCurBitsOffset, int* nCurBitShift, int* nFinalLiterals, int* nCurRepMatchOffset, const int nBlockFlags) {
1353 const salvador_match* pBestMatch = pCompressor->best_match - nStartOffset;
1354 int nRepMatchOffset = *nCurRepMatchOffset;
1355 int nOutOffset = 0;
1356 const int nMaxOffset = pCompressor->max_offset;
1357 const int nIsInverted = pCompressor->flags & FLG_IS_INVERTED;
1358 const int nIsBackward = (pCompressor->flags & FLG_IS_BACKWARD) >> 1;
1359 int nNumLiterals = 0;
1360 int nInFirstLiteralOffset = 0;
1361 int nIsFirstCommand = nBlockFlags & 1;
1362 int i;
1363
1364 for (i = nStartOffset; i < nEndOffset; ) {
1365 const salvador_match* pMatch = pBestMatch + i;
1366
1367 if (pMatch->length >= 2 || (pMatch->length == 1 && pMatch->offset == nRepMatchOffset && nNumLiterals != 0)) {
1368 const int nMatchLen = pMatch->length;
1369 const int nMatchOffset = pMatch->offset;
1370
1371 if (nMatchOffset < MIN_OFFSET || nMatchOffset > nMaxOffset || nMatchOffset > MAX_OFFSET)
1372 return -1;
1373
1374 if (nIsFirstCommand && nNumLiterals == 0) {
1375 /* The first block always starts with a literal */
1376 return -1;
1377 }
1378
1379 if (nNumLiterals != 0) {
1380 /* Literals */
1381
1382 if (nNumLiterals < pCompressor->stats.min_literals || pCompressor->stats.min_literals == -1)
1383 pCompressor->stats.min_literals = nNumLiterals;
1384 if (nNumLiterals > pCompressor->stats.max_literals)
1385 pCompressor->stats.max_literals = nNumLiterals;
1386 pCompressor->stats.total_literals += nNumLiterals;
1387 pCompressor->stats.literals_divisor++;
1388
1389 if (!nIsFirstCommand) {
1390 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, 0 /* literals follow */, nCurBitsOffset, nCurBitShift);
1391 if (nOutOffset < 0) return -1;
1392 }
1393
1394 /* The command code for subsequent literals isn't omitted */
1395 nIsFirstCommand = 0;
1396
1397 nOutOffset = salvador_write_normal_elias_value(pOutData, nOutOffset, nMaxOutDataSize, nNumLiterals, nIsBackward, nCurBitsOffset, nCurBitShift);
1398 if (nOutOffset < 0) return -1;
1399
1400 if ((nOutOffset + nNumLiterals) > nMaxOutDataSize)
1401 return -1;
1402 memcpy(pOutData + nOutOffset, pInWindow + nInFirstLiteralOffset, nNumLiterals);
1403 nOutOffset += nNumLiterals;
1404 }
1405
1406 if (nMatchOffset == nRepMatchOffset && nNumLiterals != 0) {
1407 /* Rep match */
1408 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, 0 /* rep match */, nCurBitsOffset, nCurBitShift);
1409 if (nOutOffset < 0) return -1;
1410
1411 /* Write match length */
1412 nOutOffset = salvador_write_normal_elias_value(pOutData, nOutOffset, nMaxOutDataSize, nMatchLen, nIsBackward, nCurBitsOffset, nCurBitShift);
1413 if (nOutOffset < 0) return -1;
1414 }
1415 else {
1416 /* Match with offset */
1417 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, 1 /* match with offset */, nCurBitsOffset, nCurBitShift);
1418 if (nOutOffset < 0) return -1;
1419
1420 /* Write high bits of match offset */
1421 if (nIsInverted)
1422 nOutOffset = salvador_write_inverted_elias_value(pOutData, nOutOffset, nMaxOutDataSize, ((nMatchOffset - 1) >> 7) + 1, nIsBackward, nCurBitsOffset, nCurBitShift);
1423 else
1424 nOutOffset = salvador_write_normal_elias_value(pOutData, nOutOffset, nMaxOutDataSize, ((nMatchOffset - 1) >> 7) + 1, nIsBackward, nCurBitsOffset, nCurBitShift);
1425 if (nOutOffset < 0) return -1;
1426
1427 /* Write low byte of match offset */
1428 if (nOutOffset >= nMaxOutDataSize)
1429 return -1;
1430 if (nIsBackward)
1431 pOutData[nOutOffset++] = ((nMatchOffset - 1) & 0x7f) << 1;
1432 else
1433 pOutData[nOutOffset++] = (255 - ((nMatchOffset - 1) & 0x7f)) << 1;
1434
1435 /* Write match length */
1436 if (nMatchLen > 2) {
1437 if (nIsBackward)
1438 pOutData[nOutOffset - 1] |= 1;
1439 nOutOffset = salvador_write_split_elias_value(pOutData, nOutOffset, nMaxOutDataSize, nMatchLen - 1, nIsBackward, nCurBitsOffset, nCurBitShift);
1440 if (nOutOffset < 0) return -1;
1441 }
1442 else {
1443 if (!nIsBackward)
1444 pOutData[nOutOffset - 1] |= 1;
1445 }
1446 }
1447
1448 nNumLiterals = 0;
1449
1450 if (nMatchOffset == nRepMatchOffset)
1451 pCompressor->stats.num_rep_matches++;
1452 else
1453 pCompressor->stats.num_normal_matches++;
1454
1455 nRepMatchOffset = nMatchOffset;
1456
1457 if (nMatchOffset < pCompressor->stats.min_offset || pCompressor->stats.min_offset == -1)
1458 pCompressor->stats.min_offset = nMatchOffset;
1459 if (nMatchOffset > pCompressor->stats.max_offset)
1460 pCompressor->stats.max_offset = nMatchOffset;
1461 pCompressor->stats.total_offsets += (long long)nMatchOffset;
1462
1463 if (nMatchLen < pCompressor->stats.min_match_len || pCompressor->stats.min_match_len == -1)
1464 pCompressor->stats.min_match_len = nMatchLen;
1465 if (nMatchLen > pCompressor->stats.max_match_len)
1466 pCompressor->stats.max_match_len = nMatchLen;
1467 pCompressor->stats.total_match_lens += nMatchLen;
1468 pCompressor->stats.match_divisor++;
1469
1470 if (nMatchOffset == 1) {
1471 if (nMatchLen < pCompressor->stats.min_rle1_len || pCompressor->stats.min_rle1_len == -1)
1472 pCompressor->stats.min_rle1_len = nMatchLen;
1473 if (nMatchLen > pCompressor->stats.max_rle1_len)
1474 pCompressor->stats.max_rle1_len = nMatchLen;
1475 pCompressor->stats.total_rle1_lens += nMatchLen;
1476 pCompressor->stats.rle1_divisor++;
1477 }
1478 else if (nMatchOffset == 2) {
1479 if (nMatchLen < pCompressor->stats.min_rle2_len || pCompressor->stats.min_rle2_len == -1)
1480 pCompressor->stats.min_rle2_len = nMatchLen;
1481 if (nMatchLen > pCompressor->stats.max_rle2_len)
1482 pCompressor->stats.max_rle2_len = nMatchLen;
1483 pCompressor->stats.total_rle2_lens += nMatchLen;
1484 pCompressor->stats.rle2_divisor++;
1485 }
1486
1487 i += nMatchLen;
1488
1489 const int nCurSafeDist = (i - nStartOffset) - nOutOffset;
1490 if (nCurSafeDist >= 0 && pCompressor->stats.safe_dist < nCurSafeDist)
1491 pCompressor->stats.safe_dist = nCurSafeDist;
1492
1493 pCompressor->stats.commands_divisor++;
1494 }
1495 else {
1496 if (nNumLiterals == 0)
1497 nInFirstLiteralOffset = i;
1498 nNumLiterals++;
1499 i++;
1500 }
1501 }
1502
1503 if (nBlockFlags & 2) {
1504 if (nNumLiterals < pCompressor->stats.min_literals || pCompressor->stats.min_literals == -1)
1505 pCompressor->stats.min_literals = nNumLiterals;
1506 if (nNumLiterals > pCompressor->stats.max_literals)
1507 pCompressor->stats.max_literals = nNumLiterals;
1508 pCompressor->stats.total_literals += nNumLiterals;
1509 pCompressor->stats.literals_divisor++;
1510
1511 *nFinalLiterals = 0;
1512
1513 if (nNumLiterals != 0) {
1514 /* Final Literals */
1515
1516 if (!nIsFirstCommand) {
1517 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, 0 /* literals follow */, nCurBitsOffset, nCurBitShift);
1518 if (nOutOffset < 0) return -1;
1519 }
1520
1521 nOutOffset = salvador_write_normal_elias_value(pOutData, nOutOffset, nMaxOutDataSize, nNumLiterals, nIsBackward, nCurBitsOffset, nCurBitShift);
1522 if (nOutOffset < 0) return -1;
1523
1524 if ((nOutOffset + nNumLiterals) > nMaxOutDataSize)
1525 return -1;
1526 memcpy(pOutData + nOutOffset, pInWindow + nInFirstLiteralOffset, nNumLiterals);
1527 nOutOffset += nNumLiterals;
1528 }
1529
1530 nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, 1 /* match with offset */, nCurBitsOffset, nCurBitShift);
1531 if (nOutOffset < 0) return -1;
1532
1533 if (nIsInverted)
1534 nOutOffset = salvador_write_inverted_elias_value(pOutData, nOutOffset, nMaxOutDataSize, 256 /* EOD */, nIsBackward, nCurBitsOffset, nCurBitShift);
1535 else
1536 nOutOffset = salvador_write_normal_elias_value(pOutData, nOutOffset, nMaxOutDataSize, 256 /* EOD */, nIsBackward, nCurBitsOffset, nCurBitShift);
1537 if (nOutOffset < 0) return -1;
1538
1539 pCompressor->stats.num_eod++;
1540 }
1541 else {
1542 *nFinalLiterals = nNumLiterals;
1543 }
1544
1545 *nCurRepMatchOffset = nRepMatchOffset;
1546 return nOutOffset;
1547 }
1548
1549 /**
1550 * Select the most optimal matches, reduce the token count if possible, and then emit a block of compressed data
1551 *
1552 * @param pCompressor compression context
1553 * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress)
1554 * @param nPreviousBlockSize number of previously compressed bytes (or 0 for none)
1555 * @param nInDataSize number of input bytes to compress
1556 * @param pOutData pointer to output buffer
1557 * @param nMaxOutDataSize maximum size of output buffer, in bytes
1558 * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits
1559 * @param nCurBitShift bit shift count
1560 * @param nFinalLiterals output number of literals not written after writing this block, that need to be written in the next block
1561 * @param nCurRepMatchOffset starting rep offset for this block, updated after the block is compressed successfully
1562 * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise
1563 *
1564 * @return size of compressed data in output buffer, or -1 if the data is uncompressible
1565 */
1566 static int salvador_optimize_and_write_block(salvador_compressor *pCompressor, const unsigned char *pInWindow, const int nPreviousBlockSize, const int nInDataSize, unsigned char *pOutData, const int nMaxOutDataSize, int *nCurBitsOffset, int *nCurBitShift, int *nFinalLiterals, int *nCurRepMatchOffset, const int nBlockFlags) {
1567 const int nEndOffset = nPreviousBlockSize + nInDataSize;
1568 int *rle_len = (int*)pCompressor->intervals /* reuse */;
1569 int *first_offset_for_byte = pCompressor->first_offset_for_byte;
1570 int *next_offset_for_pos = pCompressor->next_offset_for_pos;
1571 int *offset_cache = pCompressor->offset_cache;
1572 int i, nPosition;
1573
1574 memset(pCompressor->best_match, 0, pCompressor->block_size * sizeof(salvador_match));
1575
1576 /* Count identical bytes */
1577
1578 i = 0;
1579 while (i < nEndOffset) {
1580 int nRangeStartIdx = i;
1581 const unsigned char c = pInWindow[nRangeStartIdx];
1582
1583 do {
1584 i++;
1585 } while (i < nEndOffset && pInWindow[i] == c);
1586
1587 while (nRangeStartIdx < i) {
1588 rle_len[nRangeStartIdx] = i - nRangeStartIdx;
1589 nRangeStartIdx++;
1590 }
1591 }
1592
1593 /* Supplement small matches */
1594
1595 memset(first_offset_for_byte, 0xff, sizeof(int) * 65536);
1596 memset(next_offset_for_pos, 0xff, sizeof(int) * nInDataSize);
1597
1598 for (nPosition = nPreviousBlockSize; nPosition < (nEndOffset - 1); nPosition++) {
1599 next_offset_for_pos[nPosition - nPreviousBlockSize] = first_offset_for_byte[((unsigned int)pInWindow[nPosition]) | (((unsigned int)pInWindow[nPosition + 1]) << 8)];
1600 first_offset_for_byte[((unsigned int)pInWindow[nPosition]) | (((unsigned int)pInWindow[nPosition + 1]) << 8)] = nPosition;
1601 }
1602
1603 memset(offset_cache, 0xff, sizeof(int) * 2048);
1604
1605 for (nPosition = nPreviousBlockSize + 1; nPosition < (nEndOffset - 1); nPosition++) {
1606 salvador_match *match = pCompressor->match + ((nPosition - nPreviousBlockSize) * NMATCHES_PER_INDEX);
1607 const int nMaxMatchLen = ((nPosition + 130) < nEndOffset) ? 130 : (nEndOffset - nPosition);
1608 const unsigned char* pInWindowMax = pInWindow + nPosition + nMaxMatchLen;
1609 const unsigned char* pInWindowStart = pInWindow + nPosition;
1610 unsigned short *match_depth = pCompressor->match_depth + ((nPosition - nPreviousBlockSize) * NMATCHES_PER_INDEX);
1611 int m = 0;
1612 int nMatchPos;
1613
1614 while (m < 16 && match[m].length) {
1615 offset_cache[match[m].offset & 2047] = nPosition;
1616 offset_cache[(match[m].offset - match_depth[m]) & 2047] = nPosition;
1617 m++;
1618 }
1619
1620 for (nMatchPos = next_offset_for_pos[nPosition - nPreviousBlockSize]; m < 16 && nMatchPos >= 0; nMatchPos = next_offset_for_pos[nMatchPos - nPreviousBlockSize]) {
1621 const int nMatchOffset = nPosition - nMatchPos;
1622
1623 if (nMatchOffset <= pCompressor->max_offset) {
1624 int nAlreadyExists = 0;
1625
1626 if (offset_cache[nMatchOffset & 2047] == nPosition) {
1627 int nExistingMatchIdx;
1628
1629 for (nExistingMatchIdx = 0; nExistingMatchIdx < m; nExistingMatchIdx++) {
1630 if (match[nExistingMatchIdx].offset == nMatchOffset ||
1631 (match[nExistingMatchIdx].offset - match_depth[nExistingMatchIdx]) == nMatchOffset) {
1632 nAlreadyExists = 1;
1633 break;
1634 }
1635 }
1636 }
1637
1638 if (!nAlreadyExists) {
1639 const int nLen0 = rle_len[nMatchPos];
1640 const int nLen1 = rle_len[nPosition];
1641 const int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1;
1642 const unsigned char* pInWindowAtPos = pInWindowStart + nMinLen;
1643
1644 if (pInWindowAtPos > pInWindowMax)
1645 pInWindowAtPos = pInWindowMax;
1646
1647 while ((pInWindowAtPos + 8) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nMatchOffset, 8))
1648 pInWindowAtPos += 8;
1649 while ((pInWindowAtPos + 4) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nMatchOffset, 4))
1650 pInWindowAtPos += 4;
1651 while (pInWindowAtPos < pInWindowMax && pInWindowAtPos[0] == pInWindowAtPos[-nMatchOffset])
1652 pInWindowAtPos++;
1653
1654 match[m].length = (const unsigned short)(pInWindowAtPos - pInWindowStart);
1655 match[m].offset = nMatchOffset;
1656 match_depth[m] = 0;
1657 m++;
1658 }
1659 }
1660 else {
1661 break;
1662 }
1663 }
1664 }
1665
1666 /* Compress and insert additional matches */
1667 salvador_optimize_forward(pCompressor, pInWindow, nPreviousBlockSize, nEndOffset, 1 /* nInsertForwardReps */, nCurRepMatchOffset, NINITIAL_ARRIVALS_PER_POSITION, nBlockFlags);
1668
1669 /* Supplement matches further */
1670
1671 for (nPosition = nPreviousBlockSize + 1; nPosition < (nEndOffset - 1); nPosition++) {
1672 salvador_match* match = pCompressor->match + ((nPosition - nPreviousBlockSize) * NMATCHES_PER_INDEX);
1673
1674 if (match[0].length < 8) {
1675 const int nMaxMatchLen = ((nPosition + 130) < nEndOffset) ? 130 : (nEndOffset - nPosition);
1676 const unsigned char* pInWindowMax = pInWindow + nPosition + nMaxMatchLen;
1677 const unsigned char* pInWindowStart = pInWindow + nPosition;
1678 unsigned short* match_depth = pCompressor->match_depth + ((nPosition - nPreviousBlockSize) * NMATCHES_PER_INDEX);
1679 int m = 0, nInserted = 0;
1680 int nMatchPos;
1681 int nMaxForwardPos = nPosition + 2 + 1 + 3;
1682
1683 if (nMaxForwardPos > (nEndOffset - 2))
1684 nMaxForwardPos = nEndOffset - 2;
1685
1686 while (m < NMATCHES_PER_INDEX && match[m].length) {
1687 offset_cache[match[m].offset & 2047] = nPosition;
1688 offset_cache[(match[m].offset - match_depth[m]) & 2047] = nPosition;
1689 m++;
1690 }
1691
1692 for (nMatchPos = next_offset_for_pos[nPosition - nPreviousBlockSize]; m < NMATCHES_PER_INDEX && nMatchPos >= 0; nMatchPos = next_offset_for_pos[nMatchPos - nPreviousBlockSize]) {
1693 const int nMatchOffset = nPosition - nMatchPos;
1694
1695 if (nMatchOffset <= pCompressor->max_offset) {
1696 int nAlreadyExists = 0;
1697
1698 if (offset_cache[nMatchOffset & 2047] == nPosition) {
1699 int nExistingMatchIdx;
1700
1701 for (nExistingMatchIdx = 0; nExistingMatchIdx < m; nExistingMatchIdx++) {
1702 if (match[nExistingMatchIdx].offset == nMatchOffset ||
1703 (match[nExistingMatchIdx].offset - match_depth[nExistingMatchIdx]) == nMatchOffset) {
1704 nAlreadyExists = 1;
1705 break;
1706 }
1707 }
1708 }
1709
1710 if (!nAlreadyExists) {
1711 int nForwardPos = nPosition + 2 + 1;
1712
1713 if (nForwardPos >= nMatchOffset) {
1714 while (nForwardPos < nMaxForwardPos) {
1715 if (pInWindow[nForwardPos] == pInWindow[nForwardPos - nMatchOffset]) {
1716 break;
1717 }
1718 nForwardPos++;
1719 }
1720
1721 if (nForwardPos < nMaxForwardPos) {
1722 const int nLen0 = rle_len[nMatchPos];
1723 const int nLen1 = rle_len[nPosition];
1724 const int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1;
1725 const unsigned char* pInWindowAtPos = pInWindowStart + nMinLen;
1726
1727 if (pInWindowAtPos > pInWindowMax)
1728 pInWindowAtPos = pInWindowMax;
1729
1730 while ((pInWindowAtPos + 8) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nMatchOffset, 8))
1731 pInWindowAtPos += 8;
1732 while ((pInWindowAtPos + 4) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nMatchOffset, 4))
1733 pInWindowAtPos += 4;
1734 while (pInWindowAtPos < pInWindowMax && pInWindowAtPos[0] == pInWindowAtPos[-nMatchOffset])
1735 pInWindowAtPos++;
1736
1737 match[m].length = (const unsigned short)(pInWindowAtPos - pInWindowStart);
1738 match[m].offset = nMatchOffset;
1739 match_depth[m] = 0;
1740 m++;
1741
1742 salvador_insert_forward_match(pCompressor, pInWindow, nPosition, nMatchOffset, nPreviousBlockSize, nEndOffset, 8);
1743
1744 nInserted++;
1745 if (nInserted >= 10)
1746 break;
1747 }
1748 }
1749 }
1750 }
1751 else {
1752 break;
1753 }
1754 }
1755 }
1756 }
1757
1758 /* Pick final matches */
1759 salvador_optimize_forward(pCompressor, pInWindow, nPreviousBlockSize, nEndOffset, 0 /* nInsertForwardReps */, nCurRepMatchOffset, pCompressor->max_arrivals_per_position, nBlockFlags);
1760
1761 /* Apply reduction and merge pass */
1762 int nDidReduce;
1763 int nPasses = 0;
1764 do {
1765 nDidReduce = salvador_reduce_commands(pCompressor, pInWindow, nPreviousBlockSize, nEndOffset, nCurRepMatchOffset, nBlockFlags);
1766 nPasses++;
1767 } while (nDidReduce && nPasses < 20);
1768
1769 /* Write compressed block */
1770
1771 return salvador_write_block(pCompressor, pInWindow, nPreviousBlockSize, nEndOffset, pOutData, nMaxOutDataSize, nCurBitsOffset, nCurBitShift, nFinalLiterals, nCurRepMatchOffset, nBlockFlags);
1772 }
1773
1774 /* Forward declaration */
1775 static void salvador_compressor_destroy(salvador_compressor *pCompressor);
1776
1777 /**
1778 * Initialize compression context
1779 *
1780 * @param pCompressor compression context to initialize
1781 * @param nBlockSize maximum size of input data (bytes to compress only)
1782 * @param nMaxWindowSize maximum size of input data window (previously compressed bytes + bytes to compress)
1783 * @param nMaxOffset maximum match offset to use (0 for default)
1784 * @param nMaxArrivals maximum number of arrivals per position
1785 * @param nFlags compression flags
1786 *
1787 * @return 0 for success, non-zero for failure
1788 */
1789 static int salvador_compressor_init(salvador_compressor *pCompressor, const int nBlockSize, const int nMaxWindowSize, const size_t nMaxOffset, const int nMaxArrivals, const int nFlags) {
1790 int nResult;
1791
1792 nResult = divsufsort_init(&pCompressor->divsufsort_context);
1793 pCompressor->intervals = NULL;
1794 pCompressor->pos_data = NULL;
1795 pCompressor->open_intervals = NULL;
1796 pCompressor->match = NULL;
1797 pCompressor->match_depth = NULL;
1798 pCompressor->best_match = NULL;
1799 pCompressor->arrival = NULL;
1800 pCompressor->first_offset_for_byte = NULL;
1801 pCompressor->next_offset_for_pos = NULL;
1802 pCompressor->offset_cache = NULL;
1803 if (nFlags & FLG_IS_BACKWARD)
1804 pCompressor->flags = nFlags & (~FLG_IS_INVERTED);
1805 else
1806 pCompressor->flags = nFlags;
1807 pCompressor->block_size = nBlockSize;
1808 pCompressor->max_offset = nMaxOffset ? (int)nMaxOffset : MAX_OFFSET;
1809 pCompressor->max_arrivals_per_position = nMaxArrivals;
1810
1811 memset(&pCompressor->stats, 0, sizeof(pCompressor->stats));
1812 pCompressor->stats.min_match_len = -1;
1813 pCompressor->stats.min_offset = -1;
1814 pCompressor->stats.min_rle1_len = -1;
1815 pCompressor->stats.min_rle2_len = -1;
1816
1817 if (!nResult) {
1818 pCompressor->intervals = (unsigned long long *)malloc(nMaxWindowSize * sizeof(unsigned long long));
1819
1820 if (pCompressor->intervals) {
1821 pCompressor->pos_data = (unsigned long long *)malloc(nMaxWindowSize * sizeof(unsigned long long));
1822
1823 if (pCompressor->pos_data) {
1824 pCompressor->open_intervals = (unsigned long long *)malloc((LCP_AND_TAG_MAX + 1) * sizeof(unsigned long long));
1825
1826 if (pCompressor->open_intervals) {
1827 pCompressor->arrival = (salvador_arrival *)malloc((nBlockSize + 1) * nMaxArrivals * sizeof(salvador_arrival));
1828
1829 if (pCompressor->arrival) {
1830 pCompressor->best_match = (salvador_match *)malloc(nBlockSize * sizeof(salvador_match));
1831
1832 if (pCompressor->best_match) {
1833 pCompressor->match = (salvador_match *)malloc(nBlockSize * NMATCHES_PER_INDEX * sizeof(salvador_match));
1834 if (pCompressor->match) {
1835 pCompressor->match_depth = (unsigned short *)malloc(nBlockSize * NMATCHES_PER_INDEX * sizeof(unsigned short));
1836 if (pCompressor->match_depth) {
1837 pCompressor->first_offset_for_byte = (int*)malloc(65536 * sizeof(int));
1838 if (pCompressor->first_offset_for_byte) {
1839 pCompressor->next_offset_for_pos = (int*)malloc(nBlockSize * sizeof(int));
1840 if (pCompressor->next_offset_for_pos) {
1841 pCompressor->offset_cache = (int*)malloc(2048 * sizeof(int));
1842 if (pCompressor->offset_cache) {
1843 return 0;
1844 }
1845 }
1846 }
1847 }
1848 }
1849 }
1850 }
1851 }
1852 }
1853 }
1854 }
1855
1856 salvador_compressor_destroy(pCompressor);
1857 return 100;
1858 }
1859
1860 /**
1861 * Clean up compression context and free up any associated resources
1862 *
1863 * @param pCompressor compression context to clean up
1864 */
1865 static void salvador_compressor_destroy(salvador_compressor *pCompressor) {
1866 divsufsort_destroy(&pCompressor->divsufsort_context);
1867
1868 if (pCompressor->offset_cache) {
1869 free(pCompressor->offset_cache);
1870 pCompressor->offset_cache = NULL;
1871 }
1872
1873 if (pCompressor->next_offset_for_pos) {
1874 free(pCompressor->next_offset_for_pos);
1875 pCompressor->next_offset_for_pos = NULL;
1876 }
1877
1878 if (pCompressor->first_offset_for_byte) {
1879 free(pCompressor->first_offset_for_byte);
1880 pCompressor->first_offset_for_byte = NULL;
1881 }
1882
1883 if (pCompressor->match_depth) {
1884 free(pCompressor->match_depth);
1885 pCompressor->match_depth = NULL;
1886 }
1887
1888 if (pCompressor->match) {
1889 free(pCompressor->match);
1890 pCompressor->match = NULL;
1891 }
1892
1893 if (pCompressor->arrival) {
1894 free(pCompressor->arrival);
1895 pCompressor->arrival = NULL;
1896 }
1897
1898 if (pCompressor->best_match) {
1899 free(pCompressor->best_match);
1900 pCompressor->best_match = NULL;
1901 }
1902
1903 if (pCompressor->open_intervals) {
1904 free(pCompressor->open_intervals);
1905 pCompressor->open_intervals = NULL;
1906 }
1907
1908 if (pCompressor->pos_data) {
1909 free(pCompressor->pos_data);
1910 pCompressor->pos_data = NULL;
1911 }
1912
1913 if (pCompressor->intervals) {
1914 free(pCompressor->intervals);
1915 pCompressor->intervals = NULL;
1916 }
1917 }
1918
1919 /**
1920 * Compress one block of data
1921 *
1922 * @param pCompressor compression context
1923 * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress)
1924 * @param nPreviousBlockSize number of previously compressed bytes (or 0 for none)
1925 * @param nInDataSize number of input bytes to compress
1926 * @param pOutData pointer to output buffer
1927 * @param nMaxOutDataSize maximum size of output buffer, in bytes
1928 * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits
1929 * @param nCurBitShift bit shift count
1930 * @param nFinalLiterals output number of literals not written after writing this block, that need to be written in the next block
1931 * @param nCurRepMatchOffset starting rep offset for this block, updated after the block is compressed successfully
1932 * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise
1933 *
1934 * @return size of compressed data in output buffer, or -1 if the data is uncompressible
1935 */
1936 static int salvador_compressor_shrink_block(salvador_compressor *pCompressor, const unsigned char *pInWindow, const int nPreviousBlockSize, const int nInDataSize, unsigned char *pOutData, const int nMaxOutDataSize, int *nCurBitsOffset, int *nCurBitShift, int *nFinalLiterals, int *nCurRepMatchOffset, const int nBlockFlags) {
1937 int nCompressedSize;
1938
1939 if (salvador_build_suffix_array(pCompressor, pInWindow, nPreviousBlockSize + nInDataSize))
1940 nCompressedSize = -1;
1941 else {
1942 if (nPreviousBlockSize) {
1943 salvador_skip_matches(pCompressor, 0, nPreviousBlockSize);
1944 }
1945 salvador_find_all_matches(pCompressor, NMATCHES_PER_INDEX, nPreviousBlockSize, nPreviousBlockSize + nInDataSize);
1946
1947 nCompressedSize = salvador_optimize_and_write_block(pCompressor, pInWindow, nPreviousBlockSize, nInDataSize, pOutData, nMaxOutDataSize, nCurBitsOffset, nCurBitShift, nFinalLiterals, nCurRepMatchOffset, nBlockFlags);
1948 }
1949
1950 return nCompressedSize;
1951 }
1952
1953 /**
1954 * Get maximum compressed size of input(source) data
1955 *
1956 * @param nInputSize input(source) size in bytes
1957 *
1958 * @return maximum compressed size
1959 */
1960 size_t salvador_get_max_compressed_size(const size_t nInputSize) {
1961 return ((nInputSize + 65535) >> 16) * 128 + nInputSize;
1962 }
1963
1964 /**
1965 * Compress memory
1966 *
1967 * @param pInputData pointer to input(source) data to compress
1968 * @param pOutBuffer buffer for compressed data
1969 * @param nInputSize input(source) size in bytes
1970 * @param nMaxOutBufferSize maximum capacity of compression buffer
1971 * @param nFlags compression flags (set to FLG_IS_INVERTED)
1972 * @param nMaxOffset maximum match offset to use (0 for default)
1973 * @param nDictionarySize size of dictionary in front of input data (0 for none)
1974 * @param progress progress function, called after compressing each block, or NULL for none
1975 * @param pStats pointer to compression stats that are filled if this function is successful, or NULL
1976 *
1977 * @return actual compressed size, or -1 for error
1978 */
1979 size_t salvador_compress(const unsigned char *pInputData, unsigned char *pOutBuffer, const size_t nInputSize, const size_t nMaxOutBufferSize,
1980 const unsigned int nFlags, const size_t nMaxOffset, const size_t nDictionarySize, void(*progress)(long long nOriginalSize, long long nCompressedSize), salvador_stats *pStats) {
1981 salvador_compressor compressor;
1982 size_t nOriginalSize = 0;
1983 size_t nCompressedSize = 0L;
1984 int nResult;
1985 int nMaxArrivals = NMAX_ARRIVALS_PER_POSITION;
1986 int nError = 0;
1987 const int nBlockSize = (nInputSize < BLOCK_SIZE) ? ((nInputSize < 1024) ? 1024 : (int)nInputSize) : BLOCK_SIZE;
1988 const int nMaxOutBlockSize = (int)salvador_get_max_compressed_size(nBlockSize);
1989
1990 nResult = salvador_compressor_init(&compressor, nBlockSize, nBlockSize * 2, nMaxOffset, nMaxArrivals, nFlags);
1991 if (nResult != 0) {
1992 return -1;
1993 }
1994
1995 int nPreviousBlockSize = 0;
1996 int nNumBlocks = 0;
1997 int nCurBitsOffset = 0, nCurBitShift = -1, nCurFinalLiterals = 0;
1998 int nBlockFlags = 1;
1999 int nCurRepMatchOffset = 1;
2000
2001 if (nDictionarySize) {
2002 nOriginalSize = (int)nDictionarySize;
2003 nPreviousBlockSize = (int)nDictionarySize;
2004 }
2005
2006 while (nOriginalSize < nInputSize && !nError) {
2007 int nInDataSize;
2008
2009 nInDataSize = (int)(nInputSize - nOriginalSize);
2010 if (nInDataSize > nBlockSize)
2011 nInDataSize = nBlockSize;
2012
2013 if (nInDataSize > 0) {
2014 int nOutDataSize;
2015 int nOutDataEnd = (int)(nMaxOutBufferSize - nCompressedSize);
2016
2017 if (nOutDataEnd > nMaxOutBlockSize)
2018 nOutDataEnd = nMaxOutBlockSize;
2019
2020 if ((nOriginalSize + nInDataSize) >= nInputSize)
2021 nBlockFlags |= 2;
2022 nOutDataSize = salvador_compressor_shrink_block(&compressor, pInputData + nOriginalSize - nPreviousBlockSize, nPreviousBlockSize, nInDataSize, pOutBuffer + nCompressedSize, nOutDataEnd,
2023 &nCurBitsOffset, &nCurBitShift, &nCurFinalLiterals, &nCurRepMatchOffset, nBlockFlags);
2024 nBlockFlags &= (~1);
2025
2026 if (nOutDataSize >= 0 && nCurFinalLiterals >= 0 && nCurFinalLiterals < nInDataSize) {
2027 /* Write compressed block */
2028
2029 nInDataSize -= nCurFinalLiterals;
2030 nOriginalSize += nInDataSize;
2031 nCurFinalLiterals = 0;
2032 nCompressedSize += nOutDataSize;
2033 if (nCurBitShift != -1)
2034 nCurBitsOffset -= nOutDataSize;
2035 }
2036 else {
2037 nError = -1;
2038 }
2039
2040 nPreviousBlockSize = nInDataSize;
2041 nNumBlocks++;
2042 }
2043
2044 if (!nError && nOriginalSize < nInputSize) {
2045 if (progress)
2046 progress(nOriginalSize, nCompressedSize);
2047 }
2048 }
2049
2050 if (progress)
2051 progress(nOriginalSize, nCompressedSize);
2052 if (pStats)
2053 *pStats = compressor.stats;
2054
2055 salvador_compressor_destroy(&compressor);
2056
2057 if (nError) {
2058 return -1;
2059 }
2060 else {
2061 return nCompressedSize;
2062 }
2063 }
This webpage is intended to be an accessible preview of this repository. To get a fuller picture, clone it and use the git CLI.