Source code

001package squidpony;
002
003import squidpony.annotation.Beta;
004import squidpony.squidmath.CoordPacker;
005
006/**
007 * Very early way of additional compression that can be applied to 2D double and byte arrays. This doesn't compress a
008 * well as using {@link LZSEncoding} on a simply-serialized String produced by {@link Converters#convertArrayDouble2D},
009 * but you can use LZSEncoding on the results of this class to significantly reduce output size. Testing on a heat map
010 * of byte values from -128 to 127 from a world map:
011 * <pre>
012 * Base size   : 1143142 // this is an uncompressed String produced by Converters
013 * LZS size    : 89170   // this uses LZSEncoding alone on the above Base string
014 * Custom size : 216209  // this uses GridCompression alone
015 * Both size   : 43120   // this uses GridCompression followed by LZSEncoding
016 * </pre>
017 * <br>
018 * This class is marked Beta because it still has some improvement that can be done on it, like having more support for
019 * other array types.
020 * <br>
021 * Created by Tommy Ettinger on 4/27/2020.
022 */
023@Beta
024public class GridCompression {
025    public static String compress(double[][] grid)
026    {
027        return compress(doubleToByteGrid(grid));
028    }
029    public static String compress(byte[][] grid)
030    {
031        CoordPacker.init();
032        final int width = grid.length, height = grid[0].length;
033        StringBuilder[] packs = new StringBuilder[8];
034        for (int i = 0; i < 8; i++) {
035            packs[i] = new StringBuilder(width * height >> 3);
036        }
037        StringBuilder packing = new StringBuilder(width * height + 128);
038        StringKit.appendHex(packing, width);
039        StringKit.appendHex(packing, height);
040        final int chunksX = width + 255 >> 8, chunksY = height + 127 >> 7;
041        short[] skip = new short[8];
042        boolean[] on = new boolean[8];
043        for (int bigX = 0, baseX = 0; bigX < chunksX; bigX++, baseX += 256) {
044            for (int bigY = 0, baseY = 0; bigY < chunksY; bigY++, baseY += 128) {
045                for (int p = 0; p < 8; p++) {
046                    packs[p].append(';');
047                    skip[p] = 0;
048                    on[p] = false;
049                }
050                boolean current;
051                short hx, hy;
052                int xSize = Math.min(256, width - baseX), ySize = Math.min(128, height - baseY),
053                        limit = 0x8000, mapLimit = xSize * ySize, code;
054                if (xSize <= 128) {
055                    limit >>= 1;
056                    if (xSize <= 64) {
057                        limit >>= 1;
058                        if (ySize <= 64) {
059                            limit >>= 1;
060                            if (ySize <= 32) {
061                                limit >>= 1;
062                                if (xSize <= 32) {
063                                    limit >>= 1;
064                                }
065                            }
066                        }
067                    }
068                }
069                for (int i = 0, ml = 0; i < limit && ml < mapLimit; i++) {
070                    hx = CoordPacker.hilbertX[i];
071                    hy = CoordPacker.hilbertY[i];
072                    if (hx >= xSize || hy >= ySize) {
073                        for (int p = 0; p < 8; p++) {
074                            if (on[p]) {
075                                on[p] = false;
076                                packs[p].append((char) (skip[p] + 256));
077                                skip[p] = 0;
078                            }
079                        }
080                        for (int p = 0; p < 8; p++) {
081                            skip[p]++;
082                        }
083                        continue;
084                    }
085                    ml++;
086                    code = (grid[baseX + hx][baseY + hy] & 255);
087                    code ^= code >>> 1; // gray code; ensures only one bit changes between consecutive bytes
088                    for (int p = 0; p < 8; p++) {
089                        current = (code >>> p & 1) == 1;
090                        if (current != on[p]) {
091                            packs[p].append((char) (skip[p] + 256));
092                            skip[p] = 0;
093                            on[p] = current;
094                        }
095                    }
096                    for (int p = 0; p < 8; p++) {
097                        skip[p]++;
098                    }
099                }
100                for (int p = 0; p < 8; p++) {
101                    if (on[p])
102                    {
103                        packs[p].append((char) (skip[p] + 256));
104                    }
105                }
106            }
107        }
108        packing.append(packs[0]);
109        for (int p = 1; p < 8; p++) {
110            packing.append('.').append(packs[p]);
111        }
112        return packing.toString();
113    }
114    public static byte[][] decompress(String compressed)
115    {
116        CoordPacker.init();
117        final int width = StringKit.intFromHex(compressed), height = StringKit.intFromHex(compressed, 8, 16);
118        byte[][] target = new byte[width][height];
119        final int chunksX = width + 255 >> 8, chunksY = height + 127 >> 7;
120        int startPack = 16, endPack, endLayer, idx;
121        boolean on;
122        for (int b = 0; b < 8; b++) {
123            endLayer = compressed.indexOf('.', startPack+1);
124            if (endLayer < 0) endLayer = compressed.length();
125            for (int bigX = 0, baseX = 0; bigX < chunksX; bigX++, baseX += 256) {
126                for (int bigY = 0, baseY = 0; bigY < chunksY; bigY++, baseY += 128) {
127                    ++startPack;
128                    endPack = Math.min(endLayer, compressed.indexOf(';', startPack));
129                    if (endPack < 0) endPack = endLayer;
130                    on = false;
131                    idx = 0;
132                    for (int p = startPack; p < endPack; p++, on = !on) {
133                        if (on) {
134                            for (int toSkip = idx + (compressed.charAt(p) - 256); idx < toSkip && idx < 0x8000; idx++) {
135                                target[CoordPacker.hilbertX[idx] + baseX][CoordPacker.hilbertY[idx] + baseY] |= 1 << b;
136                            }
137                        } else {
138                            idx += compressed.charAt(p) - 256;
139                        }
140                    }
141                    startPack = endPack;
142                }
143            }
144            ++startPack;
145        }
146        for (int x = 0; x < width; x++) {
147            for (int y = 0; y < height; y++) {
148                int b = target[x][y] & 0xFF;
149                b ^= b >>> 1;
150                b ^= b >>> 2;
151                target[x][y] = (byte)(b ^ b >>> 4);
152            }
153        }
154        return target;
155    }
156    public static double[][] byteToDoubleGrid(byte[][] bytes) {
157        return byteToDoubleGrid(bytes, new double[bytes.length][bytes[0].length]);
158    }
159    public static double[][] byteToDoubleGrid(byte[][] bytes, double[][] doubles) {
160        final int width = Math.min(bytes.length, doubles.length),
161                height = Math.min(bytes[0].length, doubles[0].length);
162        for (int x = 0; x < width; x++) {
163            for (int y = 0; y < height; y++) {
164                doubles[x][y] = (bytes[x][y] & 0xFF) * 0x1p-8;
165            }
166        }
167        return doubles;
168    }
169    public static byte[][] doubleToByteGrid(double[][] doubles) {
170        return doubleToByteGrid(doubles, new byte[doubles.length][doubles[0].length]);
171    }
172    public static byte[][] doubleToByteGrid(double[][] doubles, byte[][] bytes) {
173        final int width = Math.min(doubles.length, bytes.length),
174                height = Math.min(doubles[0].length, bytes[0].length);
175        for (int x = 0; x < width; x++) {
176            for (int y = 0; y < height; y++) {
177                bytes[x][y] = (byte) (doubles[x][y] * 256);
178            }
179        }
180        return bytes;
181    }
182    public static byte[] doubleGridToByteArray(double[][] doubles) {
183        final int width = doubles.length, height = doubles[0].length;
184        byte[] bytes = new byte[width * height + 8];
185        bytes[0] = (byte) (width >>> 24);
186        bytes[1] = (byte) (width >>> 16);
187        bytes[2] = (byte) (width >>> 8);
188        bytes[3] = (byte) (width);
189        bytes[4] = (byte) (height >>> 24);
190        bytes[5] = (byte) (height >>> 16);
191        bytes[6] = (byte) (height >>> 8);
192        bytes[7] = (byte) (height);
193        int i = 8;
194        for (int x = 0; x < width; x++) {
195            for (int y = 0; y < height; y++) {
196                bytes[i++] = (byte)(doubles[x][y] * 256);
197            }
198        }
199        return bytes;
200    }
201    public static double[][] byteArrayToDoubleGrid(byte[] bytes) {
202        final int width = bytes[0] << 24 | (bytes[1] << 16 & 0xFF0000) | (bytes[2] << 8 & 0xFF00) | (bytes[3] & 0xFF),
203                height = bytes[4] << 24 | (bytes[5] << 16 & 0xFF0000) | (bytes[6] << 8 & 0xFF00) | (bytes[7] & 0xFF);
204        double[][] doubles = new double[width][height];
205        int i = 8;
206        for (int x = 0; x < width; x++) {
207            for (int y = 0; y < height; y++) {
208                doubles[x][y] = (bytes[i++] & 0xFF) * 0x1p-8;
209            }
210        }
211        return doubles;
212    }
213
214    public static byte[] byteGridToByteArray(byte[][] grid) {
215        final int width = grid.length, height = grid[0].length;
216        byte[] bytes = new byte[width * height + 8];
217        bytes[0] = (byte) (width >>> 24);
218        bytes[1] = (byte) (width >>> 16);
219        bytes[2] = (byte) (width >>> 8);
220        bytes[3] = (byte) (width);
221        bytes[4] = (byte) (height >>> 24);
222        bytes[5] = (byte) (height >>> 16);
223        bytes[6] = (byte) (height >>> 8);
224        bytes[7] = (byte) (height);
225        int i = 8;
226        for (int x = 0; x < width; x++) {
227            for (int y = 0; y < height; y++) {
228                bytes[i++] = grid[x][y];
229            }
230        }
231        return bytes;
232    }
233    public static byte[][] byteArrayToByteGrid(byte[] bytes) {
234        final int width = bytes[0] << 24 | (bytes[1] << 16 & 0xFF0000) | (bytes[2] << 8 & 0xFF00) | (bytes[3] & 0xFF),
235                height = bytes[4] << 24 | (bytes[5] << 16 & 0xFF0000) | (bytes[6] << 8 & 0xFF00) | (bytes[7] & 0xFF);
236        byte[][] grid = new byte[width][height];
237        int i = 8;
238        for (int x = 0; x < width; x++) {
239            for (int y = 0; y < height; y++) {
240                grid[x][y] = bytes[i++];
241            }
242        }
243        return grid;
244    }
245
246}