/* * shrink.c - compressor implementation * * Copyright (C) 2021 Emmanuel Marty * * This software is provided 'as-is', without any express or implied * warranty. In no event will the authors be held liable for any damages * arising from the use of this software. * * Permission is granted to anyone to use this software for any purpose, * including commercial applications, and to alter it and redistribute it * freely, subject to the following restrictions: * * 1. The origin of this software must not be misrepresented; you must not * claim that you wrote the original software. If you use this software * in a product, an acknowledgment in the product documentation would be * appreciated but is not required. * 2. Altered source versions must be plainly marked as such, and must not be * misrepresented as being the original software. * 3. This notice may not be removed or altered from any source distribution. */ /* * Uses the libdivsufsort library Copyright (c) 2003-2008 Yuta Mori * * Implements the ZX0 encoding designed by Einar Saukas. https://github.com/einar-saukas/ZX0 * Also inspired by Charles Bloom's compression blog. http://cbloomrants.blogspot.com/ * */ #include #include #include #include "libsalvador.h" #include "matchfinder.h" #include "shrink.h" #include "format.h" #define MIN_ENCODED_MATCH_SIZE 2 #define TOKEN_SIZE 1 #define OFFSET_COST(__offset) (((__offset) <= 128) ? 8 : (7 + salvador_get_elias_size((((__offset) - 1) >> 7) + 1))) /** Costs, per length */ static const char salvador_cost_for_len[8192] = { 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, 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, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, }; /** * Get the number of bits required to encode a gamma value * * @param nValue value to encode as gamma * * @return number of bits required for encoding */ static int salvador_get_elias_size(const int nValue) { if (nValue >= 0 && nValue < 8192) { return salvador_cost_for_len[nValue] - TOKEN_SIZE; } else { int i = nValue; int nBits = 0; i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); i = (i - (i >> 1)); while ((i >>= 1) > 0) { nBits++; nBits++; } nBits++; return nBits; } } /** * Write packed 0 control bit to output (compressed) buffer * * @param pOutData pointer to output buffer * @param nOutOffset current write index into output buffer * @param nMaxOutDataSize maximum size of output buffer, in bytes * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits * @param nCurBitShift bit shift count * * @return updated write index into output buffer, or -1 in case of an error */ static int salvador_write_zero_ctrl_bit(unsigned char *pOutData, int nOutOffset, const int nMaxOutDataSize, int *nCurBitsOffset, int *nCurBitShift) { if (nOutOffset >= 0) { if ((*nCurBitShift) == -1) { /* Allocate a new byte in the stream to pack bits in */ if (nOutOffset >= nMaxOutDataSize) return -1; (*nCurBitsOffset) = nOutOffset; (*nCurBitShift) = 7; pOutData[nOutOffset++] = 0; } (*nCurBitShift)--; } return nOutOffset; } /** * Write packed 1 control bit to output (compressed) buffer * * @param pOutData pointer to output buffer * @param nOutOffset current write index into output buffer * @param nMaxOutDataSize maximum size of output buffer, in bytes * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits * @param nCurBitShift bit shift count * * @return updated write index into output buffer, or -1 in case of an error */ static int salvador_write_one_ctrl_bit(unsigned char* pOutData, int nOutOffset, const int nMaxOutDataSize, int* nCurBitsOffset, int* nCurBitShift) { if (nOutOffset >= 0) { if ((*nCurBitShift) == -1) { /* Allocate a new byte in the stream to pack bits in */ if (nOutOffset >= nMaxOutDataSize) return -1; (*nCurBitsOffset) = nOutOffset; (*nCurBitShift) = 7; pOutData[nOutOffset++] = 0; } pOutData[(*nCurBitsOffset)] |= 1 << ((*nCurBitShift)--); } return nOutOffset; } /** * Write packed data bit to output (compressed) buffer * * @param pOutData pointer to output buffer * @param nOutOffset current write index into output buffer * @param nMaxOutDataSize maximum size of output buffer, in bytes * @param nValue bit value to write * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits * @param nCurBitShift bit shift count * * @return updated write index into output buffer, or -1 in case of an error */ static int salvador_write_data_bit(unsigned char* pOutData, const int nOutOffset, const int nMaxOutDataSize, const int nValue, const int* nCurBitsOffset, int* nCurBitShift) { if (nOutOffset >= 0) { pOutData[(*nCurBitsOffset)] |= nValue << ((*nCurBitShift)--); } return nOutOffset; } /** * Write normally encoded, interlaced elias gamma value to output (compressed) buffer * * @param pOutData pointer to output buffer * @param nOutOffset current write index into output buffer * @param nMaxOutDataSize maximum size of output buffer, in bytes * @param nValue value to write with gamma encoding * @param nBackward 1 for backward compression, 0 for forward compression * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits * @param nCurBitShift bit shift count * * @return updated write index into output buffer, or -1 in case of an error */ 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) { int i = nValue; i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); i = (i - (i >> 1)); if (nBackward) { while ((i >>= 1) > 0) { nOutOffset = salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 1 : 0, nCurBitsOffset, nCurBitShift); } return salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); } else { while ((i >>= 1) > 0) { nOutOffset = salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 1 : 0, nCurBitsOffset, nCurBitShift); } return salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); } } /** * Write inverted, interlaced elias gamma value to output (compressed) buffer * * @param pOutData pointer to output buffer * @param nOutOffset current write index into output buffer * @param nMaxOutDataSize maximum size of output buffer, in bytes * @param nValue value to write with gamma encoding * @param nBackward 1 for backward compression, 0 for forward compression * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits * @param nCurBitShift bit shift count * * @return updated write index into output buffer, or -1 in case of an error */ 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) { int i = nValue; i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); i = (i - (i >> 1)); if (nBackward) { while ((i >>= 1) > 0) { nOutOffset = salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 0 : 1, nCurBitsOffset, nCurBitShift); } return salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); } else { while ((i >>= 1) > 0) { nOutOffset = salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 0 : 1, nCurBitsOffset, nCurBitShift); } return salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); } } /** * Write elias gamma encoded value to output (compressed) buffer, with the first bit stored in a different (match offset) byte * * @param pOutData pointer to output buffer * @param nOutOffset current write index into output buffer * @param nMaxOutDataSize maximum size of output buffer, in bytes * @param nValue value to write with gamma encoding * @param nBackward 1 for backward compression, 0 for forward compression * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits * @param nCurBitShift bit shift count * * @return updated write index into output buffer, or -1 in case of an error */ 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) { int i = nValue; i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); i = (i - (i >> 1)); i >>= 1; nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 1 : 0, nCurBitsOffset, nCurBitShift); if (nBackward) { while ((i >>= 1) > 0) { nOutOffset = salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 1 : 0, nCurBitsOffset, nCurBitShift); } return salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); } else { while ((i >>= 1) > 0) { nOutOffset = salvador_write_zero_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, (nValue & i) ? 1 : 0, nCurBitsOffset, nCurBitShift); } return salvador_write_one_ctrl_bit(pOutData, nOutOffset, nMaxOutDataSize, nCurBitsOffset, nCurBitShift); } } /** * Get the number of extra bits required to represent a literals length * * @param nLength literals length * * @return number of extra bits required */ static inline int salvador_get_literals_varlen_size(const int nLength) { if (nLength >= 0 && nLength < 8192) return salvador_cost_for_len[nLength]; else return TOKEN_SIZE + salvador_get_elias_size(nLength); } /** * Get the number of extra bits required to represent a non-rep match length * * @param __nLength actual match length * * @return number of extra bits required */ #define salvador_get_match_varlen_size_norep(__nLength) salvador_get_elias_size((__nLength) - 1) /** * Get the number of extra bits required to represent a repmatch length * * @param __nLength actual match length * * @return number of extra bits required */ #define salvador_get_match_varlen_size_rep(__nLength) salvador_get_elias_size(__nLength) /** * Insert forward rep candidate * * @param pCompressor compression context * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress) * @param i input data window position whose matches are being considered * @param nMatchOffset match offset to use as rep candidate * @param nStartOffset current offset in input window (typically the number of previously compressed bytes) * @param nEndOffset offset to end finding matches at (typically the size of the total input window in bytes * @param nDepth current insertion depth */ 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) { const salvador_arrival *arrival = pCompressor->arrival + ((i - nStartOffset) * pCompressor->max_arrivals_per_position); const int *rle_len = (const int*)pCompressor->intervals /* reuse */; salvador_visited* visited = ((salvador_visited*)pCompressor->pos_data) - nStartOffset /* reuse */; int j; for (j = 0; j < NINITIAL_ARRIVALS_PER_POSITION && arrival[j].from_slot; j++) { if (arrival[j].num_literals) { const int nRepOffset = arrival[j].rep_offset; if (nMatchOffset != nRepOffset) { const int nRepPos = arrival[j].rep_pos; if (nRepPos >= nStartOffset && nRepPos < nEndOffset && visited[nRepPos] != nMatchOffset) { visited[nRepPos] = nMatchOffset; salvador_match* fwd_match = pCompressor->match + ((nRepPos - nStartOffset) * NMATCHES_PER_INDEX); if (fwd_match[NMATCHES_PER_INDEX - 1].length == 0) { if (nRepPos >= nMatchOffset) { const unsigned char* pInWindowStart = pInWindow + nRepPos; if (pInWindowStart[0] == pInWindowStart[-nMatchOffset]) { if (nRepOffset) { unsigned int nMaxRepLen = nEndOffset - nRepPos; if (nMaxRepLen > LCP_MAX) nMaxRepLen = LCP_MAX; const unsigned char* pInWindowMax = pInWindowStart + nMaxRepLen; const int nLen0 = rle_len[nRepPos - nMatchOffset]; const int nLen1 = rle_len[nRepPos]; unsigned int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1, r; for (r = 0; fwd_match[r].length; r++) { if (fwd_match[r].offset == nMatchOffset) { if (nMinLen < fwd_match[r].length) nMinLen = fwd_match[r].length; break; } } const unsigned char* pInWindowAtRepOffset = pInWindowStart + nMinLen; if (pInWindowAtRepOffset > pInWindowMax) pInWindowAtRepOffset = pInWindowMax; while ((pInWindowAtRepOffset + 8) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nMatchOffset, 8)) pInWindowAtRepOffset += 8; while ((pInWindowAtRepOffset + 4) < pInWindowMax && !memcmp(pInWindowAtRepOffset, pInWindowAtRepOffset - nMatchOffset, 4)) pInWindowAtRepOffset += 4; while (pInWindowAtRepOffset < pInWindowMax && pInWindowAtRepOffset[0] == pInWindowAtRepOffset[-nMatchOffset]) pInWindowAtRepOffset++; const unsigned short nCurRepLen = (const unsigned short)(pInWindowAtRepOffset - pInWindowStart); unsigned short* fwd_depth = pCompressor->match_depth + ((nRepPos - nStartOffset) * NMATCHES_PER_INDEX); if (!fwd_match[r].length) { fwd_match[r].length = nCurRepLen; fwd_match[r].offset = nMatchOffset; fwd_depth[r] = 0; if (nDepth < 9) salvador_insert_forward_match(pCompressor, pInWindow, nRepPos, nMatchOffset, nStartOffset, nEndOffset, nDepth + 1); } else { if (fwd_match[r].length < nCurRepLen && fwd_depth[r] == 0) { fwd_match[r].length = nCurRepLen; } } } } } } } } } } } /** * Attempt to pick optimal matches, so as to produce the smallest possible output that decompresses to the same input * * @param pCompressor compression context * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress) * @param nStartOffset current offset in input window (typically the number of previously compressed bytes) * @param nEndOffset offset to end finding matches at (typically the size of the total input window in bytes * @param nInsertForwardReps non-zero to insert forward repmatch candidates, zero to use the previously inserted candidates * @param nCurRepMatchOffset starting rep offset for this block * @param nArrivalsPerPosition number of arrivals to record per input buffer position * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise */ 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) { const int nMaxArrivalsPerPosition = pCompressor->max_arrivals_per_position; salvador_arrival *arrival = pCompressor->arrival - (nStartOffset * nMaxArrivalsPerPosition); const int* rle_len = (const int*)pCompressor->intervals /* reuse */; salvador_arrival* cur_arrival; int i; if ((nEndOffset - nStartOffset) > pCompressor->block_size) return; for (i = (nStartOffset * nMaxArrivalsPerPosition); i != ((nEndOffset + 1) * nMaxArrivalsPerPosition); i += nMaxArrivalsPerPosition) { int j; memset(arrival + i, 0, sizeof(salvador_arrival) * nMaxArrivalsPerPosition); for (j = 0; j < nMaxArrivalsPerPosition; j++) arrival[i + j].cost = 0x40000000; } arrival[nStartOffset * nMaxArrivalsPerPosition].cost = 0; arrival[nStartOffset * nMaxArrivalsPerPosition].from_slot = -1; arrival[nStartOffset * nMaxArrivalsPerPosition].rep_offset = *nCurRepMatchOffset; if (nInsertForwardReps) { salvador_visited* visited = ((salvador_visited*)pCompressor->pos_data) - nStartOffset /* reuse */; memset(visited + nStartOffset, 0, (nEndOffset - nStartOffset) * sizeof(salvador_visited)); } for (i = nStartOffset, cur_arrival = &arrival[nStartOffset * nMaxArrivalsPerPosition]; i != nEndOffset; i++, cur_arrival += nMaxArrivalsPerPosition) { salvador_arrival *pDestLiteralSlots = &cur_arrival[nMaxArrivalsPerPosition]; int j, m; for (j = 0; j < nArrivalsPerPosition && cur_arrival[j].from_slot; j++) { const int nNumLiterals = cur_arrival[j].num_literals + 1; const int nCodingChoiceCost = cur_arrival[j].cost + 8 /* literal */ + (((nNumLiterals & (nNumLiterals - 1)) == 0) ? 2 : 0); const int nScore = cur_arrival[j].score + 1; const int nRepOffset = cur_arrival[j].rep_offset; if (nCodingChoiceCost < pDestLiteralSlots[nArrivalsPerPosition - 1].cost || (nCodingChoiceCost == pDestLiteralSlots[nArrivalsPerPosition - 1].cost && nScore < pDestLiteralSlots[nArrivalsPerPosition - 1].score && nRepOffset != pDestLiteralSlots[nArrivalsPerPosition - 1].rep_offset)) { int exists = 0, n; for (n = 0; pDestLiteralSlots[n].cost < nCodingChoiceCost; n++) { if (pDestLiteralSlots[n].rep_offset == nRepOffset) { exists = 1; break; } } if (!exists) { for (; pDestLiteralSlots[n].cost == nCodingChoiceCost && nScore >= pDestLiteralSlots[n].score; n++) { if (pDestLiteralSlots[n].rep_offset == nRepOffset) { exists = 1; break; } } if (!exists) { int z; for (z = n; z < nArrivalsPerPosition - 1 && pDestLiteralSlots[z].cost == nCodingChoiceCost; z++) { if (pDestLiteralSlots[z].rep_offset == nRepOffset) { exists = 1; break; } } if (!exists) { for (; z < nArrivalsPerPosition - 1 && pDestLiteralSlots[z].from_slot; z++) { if (pDestLiteralSlots[z].rep_offset == nRepOffset) break; } memmove(&pDestLiteralSlots[n + 1], &pDestLiteralSlots[n], sizeof(salvador_arrival) * (z - n)); salvador_arrival* pDestArrival = &pDestLiteralSlots[n]; pDestArrival->cost = nCodingChoiceCost; pDestArrival->from_pos = i; pDestArrival->from_slot = j + 1; pDestArrival->rep_offset = nRepOffset; pDestArrival->rep_pos = cur_arrival[j].rep_pos; pDestArrival->match_len = 0; pDestArrival->num_literals = nNumLiterals; pDestArrival->score = nScore; } } } } } if (i == nStartOffset && (nBlockFlags & 1)) continue; const int nNumArrivalsForThisPos = j; int nOverallMinRepLen = 0, nOverallMaxRepLen = 0; int nRepMatchArrivalIdx[(2 * NMAX_ARRIVALS_PER_POSITION) + 1]; int nNumRepMatchArrivals = 0; if (i < nEndOffset) { unsigned int nMaxRepLenForPos = nEndOffset - i; if (nMaxRepLenForPos > LCP_MAX) nMaxRepLenForPos = LCP_MAX; const unsigned char* pInWindowStart = pInWindow + i; const unsigned char* pInWindowMax = pInWindowStart + nMaxRepLenForPos; for (j = 0; j < nNumArrivalsForThisPos; j++) { if (cur_arrival[j].num_literals) { const int nRepOffset = cur_arrival[j].rep_offset; if (i >= nRepOffset) { if (pInWindowStart[0] == pInWindowStart[-nRepOffset]) { if (nRepOffset) { const int nLen0 = rle_len[i - nRepOffset]; const int nLen1 = rle_len[i]; const int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1; const unsigned char* pInWindowAtPos = pInWindowStart + nMinLen; if (pInWindowAtPos > pInWindowMax) pInWindowAtPos = pInWindowMax; while ((pInWindowAtPos + 8) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nRepOffset, 8)) pInWindowAtPos += 8; while ((pInWindowAtPos + 4) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nRepOffset, 4)) pInWindowAtPos += 4; while (pInWindowAtPos < pInWindowMax && pInWindowAtPos[0] == pInWindowAtPos[-nRepOffset]) pInWindowAtPos++; const int nCurRepLen = (const int)(pInWindowAtPos - pInWindowStart); if (nOverallMaxRepLen < nCurRepLen) nOverallMaxRepLen = nCurRepLen; nRepMatchArrivalIdx[nNumRepMatchArrivals++] = j; nRepMatchArrivalIdx[nNumRepMatchArrivals++] = nCurRepLen; } } } } } } nRepMatchArrivalIdx[nNumRepMatchArrivals] = -1; const salvador_match* match = pCompressor->match + ((i - nStartOffset) * NMATCHES_PER_INDEX); const unsigned short* match_depth = pCompressor->match_depth + ((i - nStartOffset) * NMATCHES_PER_INDEX); for (m = 0; m < NMATCHES_PER_INDEX && match[m].length; m++) { int nOrigMatchLen = match[m].length; const int nOrigMatchOffset = match[m].offset; const unsigned int nOrigMatchDepth = match_depth[m]; unsigned int d; if ((i + nOrigMatchLen) > nEndOffset) nOrigMatchLen = nEndOffset - i; for (d = 0; d <= nOrigMatchDepth; d += (nOrigMatchDepth ? nOrigMatchDepth : 1)) { const int nMatchLen = nOrigMatchLen - d; const int nMatchOffset = nOrigMatchOffset - d; int nNonRepMatchArrivalIdx, nStartingMatchLen, k; if (nInsertForwardReps) { salvador_insert_forward_match(pCompressor, pInWindow, i, nMatchOffset, nStartOffset, nEndOffset, 0); } nNonRepMatchArrivalIdx = -1; for (j = 0; j < nNumArrivalsForThisPos; j++) { const int nRepOffset = cur_arrival[j].rep_offset; if (nMatchOffset != nRepOffset || cur_arrival[j].num_literals == 0) { nNonRepMatchArrivalIdx = j; break; } } if (nNonRepMatchArrivalIdx >= 0) { const int nNoRepmatchOffsetCost = cur_arrival[nNonRepMatchArrivalIdx].cost /* the actual cost of the literals themselves accumulates up the chain */ + OFFSET_COST(nMatchOffset); const int nNoRepmatchScore = cur_arrival[nNonRepMatchArrivalIdx].score + 3; /* Insert non-repmatch candidate */ if (nMatchLen < LEAVE_ALONE_MATCH_SIZE) { nStartingMatchLen = 2; } else { nStartingMatchLen = nMatchLen; } for (k = nStartingMatchLen; k <= nMatchLen; k++) { salvador_arrival* pDestSlots = &cur_arrival[k * nMaxArrivalsPerPosition]; const int nMatchLenCost = (k < 8192) ? salvador_cost_for_len[k - 1] : (salvador_get_match_varlen_size_norep(k) + TOKEN_SIZE /* token */); const int nCodingChoiceCost = nMatchLenCost + nNoRepmatchOffsetCost; if (nCodingChoiceCost < pDestSlots[nArrivalsPerPosition - 2].cost || (nCodingChoiceCost == pDestSlots[nArrivalsPerPosition - 2].cost && nNoRepmatchScore < pDestSlots[nArrivalsPerPosition - 2].score && (nCodingChoiceCost != pDestSlots[nArrivalsPerPosition - 1].cost || nMatchOffset != pDestSlots[nArrivalsPerPosition - 1].rep_offset))) { int exists = 0, n; for (n = 0; pDestSlots[n].cost < nCodingChoiceCost; n++) { if (pDestSlots[n].rep_offset == nMatchOffset) { exists = 1; break; } } if (!exists) { for (; pDestSlots[n].cost == nCodingChoiceCost && nNoRepmatchScore >= pDestSlots[n].score; n++) { if (pDestSlots[n].rep_offset == nMatchOffset) { exists = 1; break; } } if (!exists) { int z; for (z = n; z < nArrivalsPerPosition - 1 && pDestSlots[z].cost == nCodingChoiceCost; z++) { if (pDestSlots[z].rep_offset == nMatchOffset) { exists = 1; break; } } if (!exists) { for (; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) { if (pDestSlots[z].rep_offset == nMatchOffset) break; } memmove(&pDestSlots[n + 1], &pDestSlots[n], sizeof(salvador_arrival) * (z - n)); salvador_arrival* pDestArrival = &pDestSlots[n]; pDestArrival->cost = nCodingChoiceCost; pDestArrival->from_pos = i; pDestArrival->from_slot = nNonRepMatchArrivalIdx + 1; pDestArrival->rep_offset = nMatchOffset; pDestArrival->rep_pos = i; pDestArrival->match_len = k; pDestArrival->num_literals = 0; pDestArrival->score = nNoRepmatchScore; } } } } } } /* Insert repmatch candidates */ if (nMatchLen < LEAVE_ALONE_MATCH_SIZE || nMatchLen <= nOverallMinRepLen) { nStartingMatchLen = nOverallMinRepLen + 1; } else { nStartingMatchLen = nMatchLen; } for (k = nStartingMatchLen; k <= (nOverallMaxRepLen < nMatchLen ? nOverallMaxRepLen : nMatchLen); k++) { const int nMatchLenCost = (k < 8192) ? salvador_cost_for_len[k] : (salvador_get_match_varlen_size_rep(k) + TOKEN_SIZE /* token */); salvador_arrival* pDestSlots = &cur_arrival[k * nMaxArrivalsPerPosition]; int nCurRepMatchArrival; for (nCurRepMatchArrival = 0; (j = nRepMatchArrivalIdx[nCurRepMatchArrival]) >= 0; nCurRepMatchArrival += 2) { if (nRepMatchArrivalIdx[nCurRepMatchArrival + 1] >= k) { const int nRepCodingChoiceCost = cur_arrival[j].cost /* the actual cost of the literals themselves accumulates up the chain */ + nMatchLenCost; const int nScore = cur_arrival[j].score + 2; const int nRepOffset = cur_arrival[j].rep_offset; if (nRepCodingChoiceCost < pDestSlots[nArrivalsPerPosition - 1].cost || (nRepCodingChoiceCost == pDestSlots[nArrivalsPerPosition - 1].cost && nScore < pDestSlots[nArrivalsPerPosition - 1].score && nRepOffset != pDestSlots[nArrivalsPerPosition - 1].rep_offset)) { int exists = 0, n; for (n = 0; pDestSlots[n].cost < nRepCodingChoiceCost; n++) { if (pDestSlots[n].rep_offset == nRepOffset) { exists = 1; break; } } if (!exists) { for (; pDestSlots[n].cost == nRepCodingChoiceCost && nScore >= pDestSlots[n].score; n++) { if (pDestSlots[n].rep_offset == nRepOffset) { exists = 1; break; } } if (!exists) { int z; for (z = n; z < nArrivalsPerPosition - 1 && pDestSlots[z].cost == nRepCodingChoiceCost; z++) { if (pDestSlots[z].rep_offset == nRepOffset) { exists = 1; break; } } if (!exists) { for (; z < nArrivalsPerPosition - 1 && pDestSlots[z].from_slot; z++) { if (pDestSlots[z].rep_offset == nRepOffset) break; } memmove(&pDestSlots[n + 1], &pDestSlots[n], sizeof(salvador_arrival) * (z - n)); salvador_arrival* pDestArrival = &pDestSlots[n]; pDestArrival->cost = nRepCodingChoiceCost; pDestArrival->from_pos = i; pDestArrival->from_slot = j + 1; pDestArrival->rep_offset = nRepOffset; pDestArrival->rep_pos = i; pDestArrival->match_len = k; pDestArrival->num_literals = 0; pDestArrival->score = nScore; } } } } else { break; } } } if (k <= LEAVE_ALONE_MATCH_SIZE) nOverallMinRepLen = k; else if (nOverallMaxRepLen == k) nOverallMaxRepLen--; } } if (nOrigMatchLen >= 1280 && ((m + 1) >= NMATCHES_PER_INDEX || match[m + 1].length < 512)) break; } } if (!nInsertForwardReps) { const salvador_arrival* end_arrival = &arrival[i * nMaxArrivalsPerPosition]; salvador_match* pBestMatch = pCompressor->best_match - nStartOffset; while (end_arrival->from_slot > 0 && end_arrival->from_pos < (const unsigned int)nEndOffset) { pBestMatch[end_arrival->from_pos].length = end_arrival->match_len; pBestMatch[end_arrival->from_pos].offset = (end_arrival->match_len) ? end_arrival->rep_offset : 0; end_arrival = &arrival[(end_arrival->from_pos * nMaxArrivalsPerPosition) + (end_arrival->from_slot - 1)]; } } } /** * Attempt to replace matches by literals when it makes the final bitstream smaller, and merge large matches * * @param pCompressor compression context * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress) * @param nStartOffset current offset in input window (typically the number of previously compressed bytes) * @param nEndOffset offset to end finding matches at (typically the size of the total input window in bytes * @param nCurRepMatchOffset starting rep offset for this block * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise * * @return non-zero if the number of tokens was reduced, 0 if it wasn't */ static int salvador_reduce_commands(salvador_compressor *pCompressor, const unsigned char *pInWindow, const int nStartOffset, const int nEndOffset, const int *nCurRepMatchOffset, const int nBlockFlags) { salvador_match* pBestMatch = pCompressor->best_match - nStartOffset; int i; int nNumLiterals = nBlockFlags & 1; int nRepMatchOffset = *nCurRepMatchOffset; int nDidReduce = 0; for (i = nStartOffset + (nBlockFlags & 1); i < nEndOffset; ) { salvador_match *pMatch = pBestMatch + i; if (pMatch->length == 0 && (i + 1) < nEndOffset && pBestMatch[i + 1].length >= MIN_ENCODED_MATCH_SIZE && pBestMatch[i + 1].length < MAX_VARLEN && pBestMatch[i + 1].offset && i >= pBestMatch[i + 1].offset && (i + pBestMatch[i + 1].length + 1) <= nEndOffset && (nNumLiterals != 0 || pBestMatch[i + 1].offset != nRepMatchOffset) && !memcmp(pInWindow + i - (pBestMatch[i + 1].offset), pInWindow + i, pBestMatch[i + 1].length + 1)) { int nCurLenSize, nReducedLenSize; if (pBestMatch[i + 1].offset == nRepMatchOffset) { nCurLenSize = salvador_get_literals_varlen_size(nNumLiterals + 1) + 8 + salvador_get_match_varlen_size_rep(pBestMatch[i + 1].length); } else { nCurLenSize = salvador_get_literals_varlen_size(nNumLiterals + 1) + 8 + salvador_get_elias_size(((pBestMatch[i + 1].offset - 1) >> 7) + 1) + 7 + salvador_get_match_varlen_size_norep(pBestMatch[i + 1].length); } if (nNumLiterals != 0 && pBestMatch[i + 1].offset == nRepMatchOffset && nRepMatchOffset) { nReducedLenSize = salvador_get_literals_varlen_size(nNumLiterals) + salvador_get_match_varlen_size_rep(pBestMatch[i + 1].length + 1); } else { nReducedLenSize = salvador_get_literals_varlen_size(nNumLiterals) + salvador_get_elias_size(((pBestMatch[i + 1].offset - 1) >> 7) + 1) + 7 + salvador_get_match_varlen_size_norep(pBestMatch[i + 1].length + 1); } if (nReducedLenSize <= nCurLenSize) { /* Merge */ pBestMatch[i].length = pBestMatch[i + 1].length + 1; pBestMatch[i].offset = pBestMatch[i + 1].offset; pBestMatch[i + 1].length = 0; pBestMatch[i + 1].offset = 0; nDidReduce = 1; continue; } } if (pMatch->length >= MIN_ENCODED_MATCH_SIZE) { if ((i + pMatch->length) < nEndOffset /* Don't consider the last match in the block, we can only reduce a match inbetween other tokens */) { int nNextIndex = i + pMatch->length; int nNextLiterals = 0; while (nNextIndex < nEndOffset && pBestMatch[nNextIndex].length == 0) { nNextLiterals++; nNextIndex++; } if (nNextIndex < nEndOffset) { /* This command is a match, is followed by 'nNextLiterals' literals and then by another match */ if (pBestMatch[nNextIndex].length >= MIN_ENCODED_MATCH_SIZE) { if (nNumLiterals != 0 && nRepMatchOffset && pMatch->offset != nRepMatchOffset && (pBestMatch[nNextIndex].offset != pMatch->offset || OFFSET_COST(pMatch->offset) > OFFSET_COST(pBestMatch[nNextIndex].offset))) { /* Check if we can get a missed backward repmatch */ if (i >= nRepMatchOffset && (i - nRepMatchOffset + pMatch->length) <= nEndOffset) { int nMaxLen = 0; while ((nMaxLen + 8) < pMatch->length && !memcmp(pInWindow + i - nRepMatchOffset + nMaxLen, pInWindow + i - pMatch->offset + nMaxLen, 8)) nMaxLen += 8; while ((nMaxLen + 4) < pMatch->length && !memcmp(pInWindow + i - nRepMatchOffset + nMaxLen, pInWindow + i - pMatch->offset + nMaxLen, 4)) nMaxLen += 4; while (nMaxLen < pMatch->length && pInWindow[i - nRepMatchOffset + nMaxLen] == pInWindow[i - pMatch->offset + nMaxLen]) nMaxLen++; if (nMaxLen >= 1) { int nCurCommandSize, nReducedCommandSize; /* -- Original: Match with offset. Skip 'match with offset follows' bit. -- */ /* High bits of match offset */ nCurCommandSize = salvador_get_elias_size(((pMatch->offset - 1) >> 7) + 1); /* Low byte of match offset */ nCurCommandSize += 7; /* Match length */ nCurCommandSize += salvador_get_match_varlen_size_norep(pMatch->length); /* Literals after command */ nCurCommandSize += salvador_get_literals_varlen_size(nNextLiterals); /* -- Reduced: Rep match. Skip 'rep-match follows' bit. -- */ /* Match length */ nReducedCommandSize = salvador_get_match_varlen_size_rep(nMaxLen); /* Literals after command */ nReducedCommandSize += (pMatch->length - nMaxLen) << 3; nReducedCommandSize += salvador_get_literals_varlen_size(nNextLiterals + (pMatch->length - nMaxLen)); if (nReducedCommandSize < nCurCommandSize) { int j; /* Change to repmatch */ pMatch->offset = nRepMatchOffset; for (j = nMaxLen; j < pMatch->length; j++) { pBestMatch[i + j].length = 0; } pMatch->length = nMaxLen; nDidReduce = 1; } } } } if (pBestMatch[nNextIndex].offset && pMatch->offset != pBestMatch[nNextIndex].offset && nRepMatchOffset != pBestMatch[nNextIndex].offset && nNextLiterals) { /* Otherwise, try to gain a match forward as well */ if (i >= pBestMatch[nNextIndex].offset && (i - pBestMatch[nNextIndex].offset + pMatch->length) <= nEndOffset && pMatch->offset != nRepMatchOffset) { int nMaxLen = 0; while ((nMaxLen + 8) < pMatch->length && !memcmp(pInWindow + i - pBestMatch[nNextIndex].offset + nMaxLen, pInWindow + i - pMatch->offset + nMaxLen, 8)) nMaxLen += 8; while ((nMaxLen + 4) < pMatch->length && !memcmp(pInWindow + i - pBestMatch[nNextIndex].offset + nMaxLen, pInWindow + i - pMatch->offset + nMaxLen, 4)) nMaxLen += 4; while (nMaxLen < pMatch->length && pInWindow[i - pBestMatch[nNextIndex].offset + nMaxLen] == pInWindow[i - pMatch->offset + nMaxLen]) nMaxLen++; if (nMaxLen >= pMatch->length) { /* Replace */ pMatch->offset = pBestMatch[nNextIndex].offset; nDidReduce = 1; } else if (nMaxLen >= 2) { int nPartialSizeBefore, nPartialSizeAfter; nPartialSizeBefore = salvador_get_match_varlen_size_norep(pMatch->length); nPartialSizeBefore += OFFSET_COST(pMatch->offset); nPartialSizeBefore += salvador_get_literals_varlen_size(nNextLiterals); nPartialSizeAfter = salvador_get_match_varlen_size_rep(nMaxLen); nPartialSizeAfter += salvador_get_literals_varlen_size(nNextLiterals + (pMatch->length - nMaxLen)) + ((pMatch->length - nMaxLen) << 3); if (nPartialSizeAfter < nPartialSizeBefore) { int j; /* 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 * we have calculated that this is shorter */ pMatch->offset = pBestMatch[nNextIndex].offset; for (j = nMaxLen; j < pMatch->length; j++) { pBestMatch[i + j].length = 0; } pMatch->length = nMaxLen; nDidReduce = 1; } } } } } if (pMatch->length < 9 /* Don't waste time considering large matches, they will always win over literals */) { /* Calculate this command's current cost */ int nCurCommandSize = salvador_get_literals_varlen_size(nNumLiterals); /* Don't include current command's literal databits */ if (pMatch->offset == nRepMatchOffset && nNumLiterals != 0 && nRepMatchOffset) { /* Rep match - don't include 'rep match follows' bit */ /* Match length */ nCurCommandSize += salvador_get_match_varlen_size_rep(pMatch->length); } else { /* Match with offset - don't include 'match with offset follows' bit */ /* High bits of match offset */ nCurCommandSize += salvador_get_elias_size(((pMatch->offset - 1) >> 7) + 1); /* Low byte of match offset */ nCurCommandSize += 7; /* Match length */ nCurCommandSize += salvador_get_match_varlen_size_norep(pMatch->length); } /* Calculate the next command's current cost */ int nNextCommandSize = salvador_get_literals_varlen_size(nNextLiterals); /* Don't include next command's literal databits */ /* Rep match or match with offset follows */ nNextCommandSize += 1; if (pMatch->offset && pBestMatch[nNextIndex].offset == pMatch->offset && nNextLiterals != 0) { /* Match length */ nNextCommandSize += salvador_get_match_varlen_size_rep(pBestMatch[nNextIndex].length); } else { /* High bits of match offset */ nNextCommandSize += salvador_get_elias_size(((pBestMatch[nNextIndex].offset - 1) >> 7) + 1); /* Low byte of match offset */ nNextCommandSize += 7; /* Match length */ nNextCommandSize += salvador_get_match_varlen_size_norep(pBestMatch[nNextIndex].length); } const int nOriginalCombinedCommandSize = nCurCommandSize + nNextCommandSize; /* Calculate the cost of replacing this match command by literals + the next command with the cost of encoding these literals */ int nReducedCommandSize = (pMatch->length << 3); nReducedCommandSize += salvador_get_literals_varlen_size(nNumLiterals + pMatch->length + nNextLiterals); /* Don't include current + next command's literal databits */ if (pBestMatch[nNextIndex].offset == nRepMatchOffset && (nNumLiterals + pMatch->length + nNextLiterals) != 0 && nRepMatchOffset) { /* Rep match - don't include 'rep match follows' bit */ /* Match length */ nReducedCommandSize += salvador_get_match_varlen_size_rep(pBestMatch[nNextIndex].length); } else { /* Match with offset - don't include 'match with offset follows' bit */ /* High bits of match offset */ nReducedCommandSize += salvador_get_elias_size(((pBestMatch[nNextIndex].offset - 1) >> 7) + 1); /* Low byte of match offset */ nReducedCommandSize += 7; /* Match length */ nReducedCommandSize += salvador_get_match_varlen_size_norep(pBestMatch[nNextIndex].length); } if (nOriginalCombinedCommandSize >= nReducedCommandSize) { /* Reduce */ const int nMatchLen = pMatch->length; int j; for (j = 0; j < nMatchLen; j++) { pBestMatch[i + j].length = 0; } nDidReduce = 1; continue; } } } } if ((i + pMatch->length) < nEndOffset && pMatch->offset && pMatch->length >= MIN_ENCODED_MATCH_SIZE && pBestMatch[i + pMatch->length].offset && pBestMatch[i + pMatch->length].length >= MIN_ENCODED_MATCH_SIZE && (pMatch->length + pBestMatch[i + pMatch->length].length) <= MAX_VARLEN && (i + pMatch->length) >= pMatch->offset && (i + pMatch->length) >= pBestMatch[i + pMatch->length].offset && (i + pMatch->length + pBestMatch[i + pMatch->length].length) <= nEndOffset && !memcmp(pInWindow + i - pMatch->offset + pMatch->length, pInWindow + i + pMatch->length - pBestMatch[i + pMatch->length].offset, pBestMatch[i + pMatch->length].length)) { int nNextIndex = i + pMatch->length + pBestMatch[i + pMatch->length].length; int nNextLiterals = 0; while (nNextIndex < nEndOffset && pBestMatch[nNextIndex].length == 0) { nNextIndex++; nNextLiterals++; } int nCurPartialSize; if (pMatch->offset == nRepMatchOffset && nNumLiterals != 0) { /* Rep match. Don't include 'rep-match follows' bit. */ /* Match length */ nCurPartialSize = salvador_get_match_varlen_size_rep(pMatch->length); } else { /* Match with offset. Don't include 'match with offset follows' bit. */ /* High bits of match offset */ nCurPartialSize = salvador_get_elias_size(((pMatch->offset - 1) >> 7) + 1); /* Low byte of match offset */ nCurPartialSize += 7; /* Match length */ nCurPartialSize += salvador_get_match_varlen_size_norep(pMatch->length); } /* Match with offset */ nCurPartialSize += 1; /* match with offset */ /* High bits of match offset */ nCurPartialSize += salvador_get_elias_size(((pBestMatch[i + pMatch->length].offset - 1) >> 7) + 1); /* Low byte of match offset */ nCurPartialSize += 7; /* Match length */ nCurPartialSize += salvador_get_match_varlen_size_norep(pBestMatch[i + pMatch->length].length); if (nNextIndex < nEndOffset) { if (pBestMatch[i + pMatch->length].offset && pBestMatch[nNextIndex].offset == pBestMatch[i + pMatch->length].offset && nNextLiterals != 0) { /* Rep match. Don't include 'rep-match follows' bit. */ /* Match length */ nCurPartialSize += salvador_get_match_varlen_size_rep(pBestMatch[nNextIndex].length); } else { /* Match with offset. Don't include 'match with offset follows' bit. */ /* High bits of match offset */ nCurPartialSize += salvador_get_elias_size(((pBestMatch[nNextIndex].offset - 1) >> 7) + 1); /* Low byte of match offset */ nCurPartialSize += 7; /* Match length */ nCurPartialSize += salvador_get_match_varlen_size_norep(pBestMatch[nNextIndex].length); } } int nReducedPartialSize; if (pMatch->offset == nRepMatchOffset && nNumLiterals != 0 && nRepMatchOffset) { /* Rep match. Don't include 'rep-match follows' bit. */ /* Match length */ nReducedPartialSize = salvador_get_match_varlen_size_rep(pMatch->length + pBestMatch[i + pMatch->length].length); } else { /* Match with offset. Don't include 'match with offset follows' bit. */ /* High bits of match offset */ nReducedPartialSize = salvador_get_elias_size(((pMatch->offset - 1) >> 7) + 1); /* Low byte of match offset */ nReducedPartialSize += 7; /* Match length */ nReducedPartialSize += salvador_get_match_varlen_size_norep(pMatch->length + pBestMatch[i + pMatch->length].length); } int nCannotReduce = 0; if (nNextIndex < nEndOffset) { if (pMatch->offset && pBestMatch[nNextIndex].offset == pMatch->offset && nNextLiterals != 0) { /* Rep match. Don't include 'rep-match follows' bit. */ /* Match length */ nReducedPartialSize += salvador_get_match_varlen_size_rep(pBestMatch[nNextIndex].length); } else { if (pBestMatch[nNextIndex].length >= MIN_ENCODED_MATCH_SIZE) { /* Match with offset. Don't include 'match with offset follows' bit. */ /* High bits of match offset */ nReducedPartialSize += salvador_get_elias_size(((pBestMatch[nNextIndex].offset - 1) >> 7) + 1); /* Low byte of match offset */ nReducedPartialSize += 7; /* Match length */ nReducedPartialSize += salvador_get_match_varlen_size_norep(pBestMatch[nNextIndex].length); } else { nCannotReduce = 1; } } } if (nCurPartialSize >= nReducedPartialSize && !nCannotReduce) { const int nMatchLen = pMatch->length; /* Join */ pMatch->length += pBestMatch[i + nMatchLen].length; pBestMatch[i + nMatchLen].length = 0; pBestMatch[i + nMatchLen].offset = 0; nDidReduce = 1; continue; } } if (nNumLiterals != 0 && pMatch->offset != nRepMatchOffset && pMatch->length == MIN_ENCODED_MATCH_SIZE && nRepMatchOffset) { if ((i + MIN_ENCODED_MATCH_SIZE /* pMatch->length */) < nEndOffset) { int nNextIndex = i + MIN_ENCODED_MATCH_SIZE /* pMatch->length */; int nNextLiterals = 0; /* 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 */ while (nNextIndex < nEndOffset && pBestMatch[nNextIndex].length == 0) { nNextLiterals++; nNextIndex++; } if (nNextIndex < nEndOffset && nNextLiterals != 0 && pBestMatch[nNextIndex].length == 1 && pBestMatch[nNextIndex].offset == pMatch->offset) { int nNextNextIndex = nNextIndex + 1 /* pBestMatch[nNextIndex].length */; int nNextNextLiterals = 0; while (nNextNextIndex < nEndOffset && pBestMatch[nNextNextIndex].length == 0) { nNextNextLiterals++; nNextNextIndex++; } if (nNextNextIndex < nEndOffset && nNextNextLiterals != 0 && pBestMatch[nNextNextIndex].length >= MIN_ENCODED_MATCH_SIZE && pBestMatch[nNextNextIndex].offset != pBestMatch[nNextIndex].offset) { int nCurCommandSize, nCurRepMatchSize, nReducedCommandSize; /* First command: match with offset */ nCurCommandSize = salvador_get_literals_varlen_size(nNumLiterals); /* Don't include match with offset's literal databits */ /* Match with offset */ nCurCommandSize += 1; /* match with offset follows */ /* High bits of match offset */ nCurCommandSize += salvador_get_elias_size(((pMatch->offset - 1) >> 7) + 1); /* Low byte of match offset */ nCurCommandSize += 7; /* Match length */ nCurCommandSize += 1 /* salvador_get_match_varlen_size_norep(pMatch->length) */; /* Second command: rep-match */ nCurRepMatchSize = salvador_get_literals_varlen_size(nNextLiterals); nCurRepMatchSize += (nNextLiterals << 3); nCurRepMatchSize += 1; /* rep-match follows */ nCurRepMatchSize += 1 /* salvador_get_match_varlen_size_rep(pBestMatch[nNextIndex].length) */; /* Combined commands as literals */ nReducedCommandSize = salvador_get_literals_varlen_size(nNumLiterals + MIN_ENCODED_MATCH_SIZE /* pMatch->length */ + nNextLiterals + 1 /* pBestMatch[nNextIndex].length */); /* Don't include combined command's literal databits */ nReducedCommandSize += (MIN_ENCODED_MATCH_SIZE /* pMatch->length */ << 3); nReducedCommandSize += (nNextLiterals << 3); nReducedCommandSize += (1 /* pBestMatch[nNextIndex].length */ << 3); if ((nCurCommandSize + nCurRepMatchSize) >= nReducedCommandSize) { int j; for (j = 0; j < MIN_ENCODED_MATCH_SIZE /* pMatch->length */; j++) { pBestMatch[i + j].length = 0; } pBestMatch[nNextIndex].length = 0; nDidReduce = 1; } } } } } nRepMatchOffset = pMatch->offset; i += pMatch->length; nNumLiterals = 0; } else if (pMatch->length == 1) { if (nNumLiterals != 0) { int nNextIndex = i + 1 /* pMatch->length */; int nNextLiterals = 0; while (nNextIndex < nEndOffset && pBestMatch[nNextIndex].length == 0) { nNextLiterals++; nNextIndex++; } if (nRepMatchOffset != pMatch->offset && (nNextIndex < nEndOffset || !nDidReduce)) { pMatch->length = 0; pMatch->offset = 0; nDidReduce = 1; continue; } if (nNextLiterals != 0) { int nCurPartialSize = salvador_get_literals_varlen_size(nNumLiterals); nCurPartialSize += TOKEN_SIZE + 1 /* salvador_get_match_varlen_size_rep(pMatch->length) */; nCurPartialSize += salvador_get_literals_varlen_size(nNextLiterals); const int nReducedPartialSize = salvador_get_literals_varlen_size(nNumLiterals + 1 + nNextLiterals) + 8; if (nCurPartialSize >= nReducedPartialSize) { pMatch->length = 0; pMatch->offset = 0; nDidReduce = 1; continue; } } } nNumLiterals = 0; i++; } else { nNumLiterals++; i++; } } return nDidReduce; } /** * Emit a block of compressed data * * @param pCompressor compression context * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress) * @param nStartOffset current offset in input window (typically the number of previously compressed bytes) * @param nEndOffset offset to end finding matches at (typically the size of the total input window in bytes * @param pOutData pointer to output buffer * @param nMaxOutDataSize maximum size of output buffer, in bytes * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits * @param nCurBitShift bit shift count * @param nFinalLiterals output number of literals not written after writing this block, that need to be written in the next block * @param nCurRepMatchOffset starting rep offset for this block, updated after the block is compressed successfully * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise * * @return size of compressed data in output buffer, or -1 if the data is uncompressible */ 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) { const salvador_match* pBestMatch = pCompressor->best_match - nStartOffset; int nRepMatchOffset = *nCurRepMatchOffset; int nOutOffset = 0; const int nMaxOffset = pCompressor->max_offset; const int nIsInverted = pCompressor->flags & FLG_IS_INVERTED; const int nIsBackward = (pCompressor->flags & FLG_IS_BACKWARD) >> 1; int nNumLiterals = 0; int nInFirstLiteralOffset = 0; int nIsFirstCommand = nBlockFlags & 1; int i; for (i = nStartOffset; i < nEndOffset; ) { const salvador_match* pMatch = pBestMatch + i; if (pMatch->length >= 2 || (pMatch->length == 1 && pMatch->offset == nRepMatchOffset && nNumLiterals != 0)) { const int nMatchLen = pMatch->length; const int nMatchOffset = pMatch->offset; if (nMatchOffset < MIN_OFFSET || nMatchOffset > nMaxOffset || nMatchOffset > MAX_OFFSET) return -1; if (nIsFirstCommand && nNumLiterals == 0) { /* The first block always starts with a literal */ return -1; } if (nNumLiterals != 0) { /* Literals */ if (nNumLiterals < pCompressor->stats.min_literals || pCompressor->stats.min_literals == -1) pCompressor->stats.min_literals = nNumLiterals; if (nNumLiterals > pCompressor->stats.max_literals) pCompressor->stats.max_literals = nNumLiterals; pCompressor->stats.total_literals += nNumLiterals; pCompressor->stats.literals_divisor++; if (!nIsFirstCommand) { nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, 0 /* literals follow */, nCurBitsOffset, nCurBitShift); if (nOutOffset < 0) return -1; } /* The command code for subsequent literals isn't omitted */ nIsFirstCommand = 0; nOutOffset = salvador_write_normal_elias_value(pOutData, nOutOffset, nMaxOutDataSize, nNumLiterals, nIsBackward, nCurBitsOffset, nCurBitShift); if (nOutOffset < 0) return -1; if ((nOutOffset + nNumLiterals) > nMaxOutDataSize) return -1; memcpy(pOutData + nOutOffset, pInWindow + nInFirstLiteralOffset, nNumLiterals); nOutOffset += nNumLiterals; } if (nMatchOffset == nRepMatchOffset && nNumLiterals != 0) { /* Rep match */ nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, 0 /* rep match */, nCurBitsOffset, nCurBitShift); if (nOutOffset < 0) return -1; /* Write match length */ nOutOffset = salvador_write_normal_elias_value(pOutData, nOutOffset, nMaxOutDataSize, nMatchLen, nIsBackward, nCurBitsOffset, nCurBitShift); if (nOutOffset < 0) return -1; } else { /* Match with offset */ nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, 1 /* match with offset */, nCurBitsOffset, nCurBitShift); if (nOutOffset < 0) return -1; /* Write high bits of match offset */ if (nIsInverted) nOutOffset = salvador_write_inverted_elias_value(pOutData, nOutOffset, nMaxOutDataSize, ((nMatchOffset - 1) >> 7) + 1, nIsBackward, nCurBitsOffset, nCurBitShift); else nOutOffset = salvador_write_normal_elias_value(pOutData, nOutOffset, nMaxOutDataSize, ((nMatchOffset - 1) >> 7) + 1, nIsBackward, nCurBitsOffset, nCurBitShift); if (nOutOffset < 0) return -1; /* Write low byte of match offset */ if (nOutOffset >= nMaxOutDataSize) return -1; if (nIsBackward) pOutData[nOutOffset++] = ((nMatchOffset - 1) & 0x7f) << 1; else pOutData[nOutOffset++] = (255 - ((nMatchOffset - 1) & 0x7f)) << 1; /* Write match length */ if (nMatchLen > 2) { if (nIsBackward) pOutData[nOutOffset - 1] |= 1; nOutOffset = salvador_write_split_elias_value(pOutData, nOutOffset, nMaxOutDataSize, nMatchLen - 1, nIsBackward, nCurBitsOffset, nCurBitShift); if (nOutOffset < 0) return -1; } else { if (!nIsBackward) pOutData[nOutOffset - 1] |= 1; } } nNumLiterals = 0; if (nMatchOffset == nRepMatchOffset) pCompressor->stats.num_rep_matches++; else pCompressor->stats.num_normal_matches++; nRepMatchOffset = nMatchOffset; if (nMatchOffset < pCompressor->stats.min_offset || pCompressor->stats.min_offset == -1) pCompressor->stats.min_offset = nMatchOffset; if (nMatchOffset > pCompressor->stats.max_offset) pCompressor->stats.max_offset = nMatchOffset; pCompressor->stats.total_offsets += (long long)nMatchOffset; if (nMatchLen < pCompressor->stats.min_match_len || pCompressor->stats.min_match_len == -1) pCompressor->stats.min_match_len = nMatchLen; if (nMatchLen > pCompressor->stats.max_match_len) pCompressor->stats.max_match_len = nMatchLen; pCompressor->stats.total_match_lens += nMatchLen; pCompressor->stats.match_divisor++; if (nMatchOffset == 1) { if (nMatchLen < pCompressor->stats.min_rle1_len || pCompressor->stats.min_rle1_len == -1) pCompressor->stats.min_rle1_len = nMatchLen; if (nMatchLen > pCompressor->stats.max_rle1_len) pCompressor->stats.max_rle1_len = nMatchLen; pCompressor->stats.total_rle1_lens += nMatchLen; pCompressor->stats.rle1_divisor++; } else if (nMatchOffset == 2) { if (nMatchLen < pCompressor->stats.min_rle2_len || pCompressor->stats.min_rle2_len == -1) pCompressor->stats.min_rle2_len = nMatchLen; if (nMatchLen > pCompressor->stats.max_rle2_len) pCompressor->stats.max_rle2_len = nMatchLen; pCompressor->stats.total_rle2_lens += nMatchLen; pCompressor->stats.rle2_divisor++; } i += nMatchLen; const int nCurSafeDist = (i - nStartOffset) - nOutOffset; if (nCurSafeDist >= 0 && pCompressor->stats.safe_dist < nCurSafeDist) pCompressor->stats.safe_dist = nCurSafeDist; pCompressor->stats.commands_divisor++; } else { if (nNumLiterals == 0) nInFirstLiteralOffset = i; nNumLiterals++; i++; } } if (nBlockFlags & 2) { if (nNumLiterals < pCompressor->stats.min_literals || pCompressor->stats.min_literals == -1) pCompressor->stats.min_literals = nNumLiterals; if (nNumLiterals > pCompressor->stats.max_literals) pCompressor->stats.max_literals = nNumLiterals; pCompressor->stats.total_literals += nNumLiterals; pCompressor->stats.literals_divisor++; *nFinalLiterals = 0; if (nNumLiterals != 0) { /* Final Literals */ if (!nIsFirstCommand) { nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, 0 /* literals follow */, nCurBitsOffset, nCurBitShift); if (nOutOffset < 0) return -1; } nOutOffset = salvador_write_normal_elias_value(pOutData, nOutOffset, nMaxOutDataSize, nNumLiterals, nIsBackward, nCurBitsOffset, nCurBitShift); if (nOutOffset < 0) return -1; if ((nOutOffset + nNumLiterals) > nMaxOutDataSize) return -1; memcpy(pOutData + nOutOffset, pInWindow + nInFirstLiteralOffset, nNumLiterals); nOutOffset += nNumLiterals; } nOutOffset = salvador_write_data_bit(pOutData, nOutOffset, nMaxOutDataSize, 1 /* match with offset */, nCurBitsOffset, nCurBitShift); if (nOutOffset < 0) return -1; if (nIsInverted) nOutOffset = salvador_write_inverted_elias_value(pOutData, nOutOffset, nMaxOutDataSize, 256 /* EOD */, nIsBackward, nCurBitsOffset, nCurBitShift); else nOutOffset = salvador_write_normal_elias_value(pOutData, nOutOffset, nMaxOutDataSize, 256 /* EOD */, nIsBackward, nCurBitsOffset, nCurBitShift); if (nOutOffset < 0) return -1; pCompressor->stats.num_eod++; } else { *nFinalLiterals = nNumLiterals; } *nCurRepMatchOffset = nRepMatchOffset; return nOutOffset; } /** * Select the most optimal matches, reduce the token count if possible, and then emit a block of compressed data * * @param pCompressor compression context * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress) * @param nPreviousBlockSize number of previously compressed bytes (or 0 for none) * @param nInDataSize number of input bytes to compress * @param pOutData pointer to output buffer * @param nMaxOutDataSize maximum size of output buffer, in bytes * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits * @param nCurBitShift bit shift count * @param nFinalLiterals output number of literals not written after writing this block, that need to be written in the next block * @param nCurRepMatchOffset starting rep offset for this block, updated after the block is compressed successfully * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise * * @return size of compressed data in output buffer, or -1 if the data is uncompressible */ 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) { const int nEndOffset = nPreviousBlockSize + nInDataSize; int *rle_len = (int*)pCompressor->intervals /* reuse */; int *first_offset_for_byte = pCompressor->first_offset_for_byte; int *next_offset_for_pos = pCompressor->next_offset_for_pos; int *offset_cache = pCompressor->offset_cache; int i, nPosition; memset(pCompressor->best_match, 0, pCompressor->block_size * sizeof(salvador_match)); /* Count identical bytes */ i = 0; while (i < nEndOffset) { int nRangeStartIdx = i; const unsigned char c = pInWindow[nRangeStartIdx]; do { i++; } while (i < nEndOffset && pInWindow[i] == c); while (nRangeStartIdx < i) { rle_len[nRangeStartIdx] = i - nRangeStartIdx; nRangeStartIdx++; } } /* Supplement small matches */ memset(first_offset_for_byte, 0xff, sizeof(int) * 65536); memset(next_offset_for_pos, 0xff, sizeof(int) * nInDataSize); for (nPosition = nPreviousBlockSize; nPosition < (nEndOffset - 1); nPosition++) { next_offset_for_pos[nPosition - nPreviousBlockSize] = first_offset_for_byte[((unsigned int)pInWindow[nPosition]) | (((unsigned int)pInWindow[nPosition + 1]) << 8)]; first_offset_for_byte[((unsigned int)pInWindow[nPosition]) | (((unsigned int)pInWindow[nPosition + 1]) << 8)] = nPosition; } memset(offset_cache, 0xff, sizeof(int) * 2048); for (nPosition = nPreviousBlockSize + 1; nPosition < (nEndOffset - 1); nPosition++) { salvador_match *match = pCompressor->match + ((nPosition - nPreviousBlockSize) * NMATCHES_PER_INDEX); const int nMaxMatchLen = ((nPosition + 130) < nEndOffset) ? 130 : (nEndOffset - nPosition); const unsigned char* pInWindowMax = pInWindow + nPosition + nMaxMatchLen; const unsigned char* pInWindowStart = pInWindow + nPosition; unsigned short *match_depth = pCompressor->match_depth + ((nPosition - nPreviousBlockSize) * NMATCHES_PER_INDEX); int m = 0; int nMatchPos; while (m < 16 && match[m].length) { offset_cache[match[m].offset & 2047] = nPosition; offset_cache[(match[m].offset - match_depth[m]) & 2047] = nPosition; m++; } for (nMatchPos = next_offset_for_pos[nPosition - nPreviousBlockSize]; m < 16 && nMatchPos >= 0; nMatchPos = next_offset_for_pos[nMatchPos - nPreviousBlockSize]) { const int nMatchOffset = nPosition - nMatchPos; if (nMatchOffset <= pCompressor->max_offset) { int nAlreadyExists = 0; if (offset_cache[nMatchOffset & 2047] == nPosition) { int nExistingMatchIdx; for (nExistingMatchIdx = 0; nExistingMatchIdx < m; nExistingMatchIdx++) { if (match[nExistingMatchIdx].offset == nMatchOffset || (match[nExistingMatchIdx].offset - match_depth[nExistingMatchIdx]) == nMatchOffset) { nAlreadyExists = 1; break; } } } if (!nAlreadyExists) { const int nLen0 = rle_len[nMatchPos]; const int nLen1 = rle_len[nPosition]; const int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1; const unsigned char* pInWindowAtPos = pInWindowStart + nMinLen; if (pInWindowAtPos > pInWindowMax) pInWindowAtPos = pInWindowMax; while ((pInWindowAtPos + 8) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nMatchOffset, 8)) pInWindowAtPos += 8; while ((pInWindowAtPos + 4) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nMatchOffset, 4)) pInWindowAtPos += 4; while (pInWindowAtPos < pInWindowMax && pInWindowAtPos[0] == pInWindowAtPos[-nMatchOffset]) pInWindowAtPos++; match[m].length = (const unsigned short)(pInWindowAtPos - pInWindowStart); match[m].offset = nMatchOffset; match_depth[m] = 0; m++; } } else { break; } } } /* Compress and insert additional matches */ salvador_optimize_forward(pCompressor, pInWindow, nPreviousBlockSize, nEndOffset, 1 /* nInsertForwardReps */, nCurRepMatchOffset, NINITIAL_ARRIVALS_PER_POSITION, nBlockFlags); /* Supplement matches further */ for (nPosition = nPreviousBlockSize + 1; nPosition < (nEndOffset - 1); nPosition++) { salvador_match* match = pCompressor->match + ((nPosition - nPreviousBlockSize) * NMATCHES_PER_INDEX); if (match[0].length < 8) { const int nMaxMatchLen = ((nPosition + 130) < nEndOffset) ? 130 : (nEndOffset - nPosition); const unsigned char* pInWindowMax = pInWindow + nPosition + nMaxMatchLen; const unsigned char* pInWindowStart = pInWindow + nPosition; unsigned short* match_depth = pCompressor->match_depth + ((nPosition - nPreviousBlockSize) * NMATCHES_PER_INDEX); int m = 0, nInserted = 0; int nMatchPos; int nMaxForwardPos = nPosition + 2 + 1 + 3; if (nMaxForwardPos > (nEndOffset - 2)) nMaxForwardPos = nEndOffset - 2; while (m < NMATCHES_PER_INDEX && match[m].length) { offset_cache[match[m].offset & 2047] = nPosition; offset_cache[(match[m].offset - match_depth[m]) & 2047] = nPosition; m++; } for (nMatchPos = next_offset_for_pos[nPosition - nPreviousBlockSize]; m < NMATCHES_PER_INDEX && nMatchPos >= 0; nMatchPos = next_offset_for_pos[nMatchPos - nPreviousBlockSize]) { const int nMatchOffset = nPosition - nMatchPos; if (nMatchOffset <= pCompressor->max_offset) { int nAlreadyExists = 0; if (offset_cache[nMatchOffset & 2047] == nPosition) { int nExistingMatchIdx; for (nExistingMatchIdx = 0; nExistingMatchIdx < m; nExistingMatchIdx++) { if (match[nExistingMatchIdx].offset == nMatchOffset || (match[nExistingMatchIdx].offset - match_depth[nExistingMatchIdx]) == nMatchOffset) { nAlreadyExists = 1; break; } } } if (!nAlreadyExists) { int nForwardPos = nPosition + 2 + 1; if (nForwardPos >= nMatchOffset) { while (nForwardPos < nMaxForwardPos) { if (pInWindow[nForwardPos] == pInWindow[nForwardPos - nMatchOffset]) { break; } nForwardPos++; } if (nForwardPos < nMaxForwardPos) { const int nLen0 = rle_len[nMatchPos]; const int nLen1 = rle_len[nPosition]; const int nMinLen = (nLen0 < nLen1) ? nLen0 : nLen1; const unsigned char* pInWindowAtPos = pInWindowStart + nMinLen; if (pInWindowAtPos > pInWindowMax) pInWindowAtPos = pInWindowMax; while ((pInWindowAtPos + 8) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nMatchOffset, 8)) pInWindowAtPos += 8; while ((pInWindowAtPos + 4) < pInWindowMax && !memcmp(pInWindowAtPos, pInWindowAtPos - nMatchOffset, 4)) pInWindowAtPos += 4; while (pInWindowAtPos < pInWindowMax && pInWindowAtPos[0] == pInWindowAtPos[-nMatchOffset]) pInWindowAtPos++; match[m].length = (const unsigned short)(pInWindowAtPos - pInWindowStart); match[m].offset = nMatchOffset; match_depth[m] = 0; m++; salvador_insert_forward_match(pCompressor, pInWindow, nPosition, nMatchOffset, nPreviousBlockSize, nEndOffset, 8); nInserted++; if (nInserted >= 10) break; } } } } else { break; } } } } /* Pick final matches */ salvador_optimize_forward(pCompressor, pInWindow, nPreviousBlockSize, nEndOffset, 0 /* nInsertForwardReps */, nCurRepMatchOffset, pCompressor->max_arrivals_per_position, nBlockFlags); /* Apply reduction and merge pass */ int nDidReduce; int nPasses = 0; do { nDidReduce = salvador_reduce_commands(pCompressor, pInWindow, nPreviousBlockSize, nEndOffset, nCurRepMatchOffset, nBlockFlags); nPasses++; } while (nDidReduce && nPasses < 20); /* Write compressed block */ return salvador_write_block(pCompressor, pInWindow, nPreviousBlockSize, nEndOffset, pOutData, nMaxOutDataSize, nCurBitsOffset, nCurBitShift, nFinalLiterals, nCurRepMatchOffset, nBlockFlags); } /* Forward declaration */ static void salvador_compressor_destroy(salvador_compressor *pCompressor); /** * Initialize compression context * * @param pCompressor compression context to initialize * @param nBlockSize maximum size of input data (bytes to compress only) * @param nMaxWindowSize maximum size of input data window (previously compressed bytes + bytes to compress) * @param nMaxOffset maximum match offset to use (0 for default) * @param nMaxArrivals maximum number of arrivals per position * @param nFlags compression flags * * @return 0 for success, non-zero for failure */ static int salvador_compressor_init(salvador_compressor *pCompressor, const int nBlockSize, const int nMaxWindowSize, const size_t nMaxOffset, const int nMaxArrivals, const int nFlags) { int nResult; nResult = divsufsort_init(&pCompressor->divsufsort_context); pCompressor->intervals = NULL; pCompressor->pos_data = NULL; pCompressor->open_intervals = NULL; pCompressor->match = NULL; pCompressor->match_depth = NULL; pCompressor->best_match = NULL; pCompressor->arrival = NULL; pCompressor->first_offset_for_byte = NULL; pCompressor->next_offset_for_pos = NULL; pCompressor->offset_cache = NULL; if (nFlags & FLG_IS_BACKWARD) pCompressor->flags = nFlags & (~FLG_IS_INVERTED); else pCompressor->flags = nFlags; pCompressor->block_size = nBlockSize; pCompressor->max_offset = nMaxOffset ? (int)nMaxOffset : MAX_OFFSET; pCompressor->max_arrivals_per_position = nMaxArrivals; memset(&pCompressor->stats, 0, sizeof(pCompressor->stats)); pCompressor->stats.min_match_len = -1; pCompressor->stats.min_offset = -1; pCompressor->stats.min_rle1_len = -1; pCompressor->stats.min_rle2_len = -1; if (!nResult) { pCompressor->intervals = (unsigned long long *)malloc(nMaxWindowSize * sizeof(unsigned long long)); if (pCompressor->intervals) { pCompressor->pos_data = (unsigned long long *)malloc(nMaxWindowSize * sizeof(unsigned long long)); if (pCompressor->pos_data) { pCompressor->open_intervals = (unsigned long long *)malloc((LCP_AND_TAG_MAX + 1) * sizeof(unsigned long long)); if (pCompressor->open_intervals) { pCompressor->arrival = (salvador_arrival *)malloc((nBlockSize + 1) * nMaxArrivals * sizeof(salvador_arrival)); if (pCompressor->arrival) { pCompressor->best_match = (salvador_match *)malloc(nBlockSize * sizeof(salvador_match)); if (pCompressor->best_match) { pCompressor->match = (salvador_match *)malloc(nBlockSize * NMATCHES_PER_INDEX * sizeof(salvador_match)); if (pCompressor->match) { pCompressor->match_depth = (unsigned short *)malloc(nBlockSize * NMATCHES_PER_INDEX * sizeof(unsigned short)); if (pCompressor->match_depth) { pCompressor->first_offset_for_byte = (int*)malloc(65536 * sizeof(int)); if (pCompressor->first_offset_for_byte) { pCompressor->next_offset_for_pos = (int*)malloc(nBlockSize * sizeof(int)); if (pCompressor->next_offset_for_pos) { pCompressor->offset_cache = (int*)malloc(2048 * sizeof(int)); if (pCompressor->offset_cache) { return 0; } } } } } } } } } } } salvador_compressor_destroy(pCompressor); return 100; } /** * Clean up compression context and free up any associated resources * * @param pCompressor compression context to clean up */ static void salvador_compressor_destroy(salvador_compressor *pCompressor) { divsufsort_destroy(&pCompressor->divsufsort_context); if (pCompressor->offset_cache) { free(pCompressor->offset_cache); pCompressor->offset_cache = NULL; } if (pCompressor->next_offset_for_pos) { free(pCompressor->next_offset_for_pos); pCompressor->next_offset_for_pos = NULL; } if (pCompressor->first_offset_for_byte) { free(pCompressor->first_offset_for_byte); pCompressor->first_offset_for_byte = NULL; } if (pCompressor->match_depth) { free(pCompressor->match_depth); pCompressor->match_depth = NULL; } if (pCompressor->match) { free(pCompressor->match); pCompressor->match = NULL; } if (pCompressor->arrival) { free(pCompressor->arrival); pCompressor->arrival = NULL; } if (pCompressor->best_match) { free(pCompressor->best_match); pCompressor->best_match = NULL; } if (pCompressor->open_intervals) { free(pCompressor->open_intervals); pCompressor->open_intervals = NULL; } if (pCompressor->pos_data) { free(pCompressor->pos_data); pCompressor->pos_data = NULL; } if (pCompressor->intervals) { free(pCompressor->intervals); pCompressor->intervals = NULL; } } /** * Compress one block of data * * @param pCompressor compression context * @param pInWindow pointer to input data window (previously compressed bytes + bytes to compress) * @param nPreviousBlockSize number of previously compressed bytes (or 0 for none) * @param nInDataSize number of input bytes to compress * @param pOutData pointer to output buffer * @param nMaxOutDataSize maximum size of output buffer, in bytes * @param nCurBitsOffset write index into output buffer, of current byte being filled with bits * @param nCurBitShift bit shift count * @param nFinalLiterals output number of literals not written after writing this block, that need to be written in the next block * @param nCurRepMatchOffset starting rep offset for this block, updated after the block is compressed successfully * @param nBlockFlags bit 0: 1 for first block, 0 otherwise; bit 1: 1 for last block, 0 otherwise * * @return size of compressed data in output buffer, or -1 if the data is uncompressible */ 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) { int nCompressedSize; if (salvador_build_suffix_array(pCompressor, pInWindow, nPreviousBlockSize + nInDataSize)) nCompressedSize = -1; else { if (nPreviousBlockSize) { salvador_skip_matches(pCompressor, 0, nPreviousBlockSize); } salvador_find_all_matches(pCompressor, NMATCHES_PER_INDEX, nPreviousBlockSize, nPreviousBlockSize + nInDataSize); nCompressedSize = salvador_optimize_and_write_block(pCompressor, pInWindow, nPreviousBlockSize, nInDataSize, pOutData, nMaxOutDataSize, nCurBitsOffset, nCurBitShift, nFinalLiterals, nCurRepMatchOffset, nBlockFlags); } return nCompressedSize; } /** * Get maximum compressed size of input(source) data * * @param nInputSize input(source) size in bytes * * @return maximum compressed size */ size_t salvador_get_max_compressed_size(const size_t nInputSize) { return ((nInputSize + 65535) >> 16) * 128 + nInputSize; } /** * Compress memory * * @param pInputData pointer to input(source) data to compress * @param pOutBuffer buffer for compressed data * @param nInputSize input(source) size in bytes * @param nMaxOutBufferSize maximum capacity of compression buffer * @param nFlags compression flags (set to FLG_IS_INVERTED) * @param nMaxOffset maximum match offset to use (0 for default) * @param nDictionarySize size of dictionary in front of input data (0 for none) * @param progress progress function, called after compressing each block, or NULL for none * @param pStats pointer to compression stats that are filled if this function is successful, or NULL * * @return actual compressed size, or -1 for error */ size_t salvador_compress(const unsigned char *pInputData, unsigned char *pOutBuffer, const size_t nInputSize, const size_t nMaxOutBufferSize, const unsigned int nFlags, const size_t nMaxOffset, const size_t nDictionarySize, void(*progress)(long long nOriginalSize, long long nCompressedSize), salvador_stats *pStats) { salvador_compressor compressor; size_t nOriginalSize = 0; size_t nCompressedSize = 0L; int nResult; int nMaxArrivals = NMAX_ARRIVALS_PER_POSITION; int nError = 0; const int nBlockSize = (nInputSize < BLOCK_SIZE) ? ((nInputSize < 1024) ? 1024 : (int)nInputSize) : BLOCK_SIZE; const int nMaxOutBlockSize = (int)salvador_get_max_compressed_size(nBlockSize); nResult = salvador_compressor_init(&compressor, nBlockSize, nBlockSize * 2, nMaxOffset, nMaxArrivals, nFlags); if (nResult != 0) { return -1; } int nPreviousBlockSize = 0; int nNumBlocks = 0; int nCurBitsOffset = 0, nCurBitShift = -1, nCurFinalLiterals = 0; int nBlockFlags = 1; int nCurRepMatchOffset = 1; if (nDictionarySize) { nOriginalSize = (int)nDictionarySize; nPreviousBlockSize = (int)nDictionarySize; } while (nOriginalSize < nInputSize && !nError) { int nInDataSize; nInDataSize = (int)(nInputSize - nOriginalSize); if (nInDataSize > nBlockSize) nInDataSize = nBlockSize; if (nInDataSize > 0) { int nOutDataSize; int nOutDataEnd = (int)(nMaxOutBufferSize - nCompressedSize); if (nOutDataEnd > nMaxOutBlockSize) nOutDataEnd = nMaxOutBlockSize; if ((nOriginalSize + nInDataSize) >= nInputSize) nBlockFlags |= 2; nOutDataSize = salvador_compressor_shrink_block(&compressor, pInputData + nOriginalSize - nPreviousBlockSize, nPreviousBlockSize, nInDataSize, pOutBuffer + nCompressedSize, nOutDataEnd, &nCurBitsOffset, &nCurBitShift, &nCurFinalLiterals, &nCurRepMatchOffset, nBlockFlags); nBlockFlags &= (~1); if (nOutDataSize >= 0 && nCurFinalLiterals >= 0 && nCurFinalLiterals < nInDataSize) { /* Write compressed block */ nInDataSize -= nCurFinalLiterals; nOriginalSize += nInDataSize; nCurFinalLiterals = 0; nCompressedSize += nOutDataSize; if (nCurBitShift != -1) nCurBitsOffset -= nOutDataSize; } else { nError = -1; } nPreviousBlockSize = nInDataSize; nNumBlocks++; } if (!nError && nOriginalSize < nInputSize) { if (progress) progress(nOriginalSize, nCompressedSize); } } if (progress) progress(nOriginalSize, nCompressedSize); if (pStats) *pStats = compressor.stats; salvador_compressor_destroy(&compressor); if (nError) { return -1; } else { return nCompressedSize; } }