import java.io.*;
import java.nio.charset.StandardCharsets;
import java.util.*;

public class Main {

    public static TreeMap<Long, Long> blocks = new TreeMap<>();
    public static Set<Long> offsets = new HashSet<>();
    public static Set<Long> block_offsets = new HashSet<>();
    public static Set<Long> block_offsets2 = new HashSet<>();
    public static long file_length;

    public static void main(String[] args) {

        try {
//            File file = new File("hello.bin");
            File file = new File("geperion2006.gmail.com.bin");

            RandomAccessFile randomAccessFile = new RandomAccessFile(file, "r");


            file_length = file.length();
            System.out.println("File length: " + file_length);
            offsets.add(0L);

            // Read first block
            block_offsets = readBlock(randomAccessFile, 0L);

            // Read rest blocks
            while (!block_offsets.isEmpty() || !block_offsets2.isEmpty()) {

                for (long offset : block_offsets) {
                    block_offsets2.addAll(readBlock(randomAccessFile, offset));
                }
                block_offsets.clear();

                for (long offset : block_offsets2) {
                    block_offsets.addAll(readBlock(randomAccessFile, offset));
                }
                block_offsets2.clear();

//                 System.out.println(blocks.size());
            }

            System.out.println("=================");

            // Print hidden message
            while (!blocks.isEmpty()) {
                Map.Entry<Long, Long> entry = blocks.pollFirstEntry();
                long last_offset = entry.getKey() + entry.getValue();
                long next_offset;

                if (!blocks.isEmpty()) {
                    next_offset = blocks.firstKey();
                } else {
                    next_offset = file_length;
                }

                if (last_offset < next_offset) {
                    int read = (int) (next_offset - last_offset);
                    try {
                        byte[] tmp = new byte[read];
                        randomAccessFile.seek(last_offset);
                        randomAccessFile.read(tmp, 0, read);

                        String str = new String(tmp, 0, read, StandardCharsets.UTF_8);
                        System.out.print(str);

                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } finally {
        }

    }

    public static Set<Long> readBlock(RandomAccessFile randomAccessFile, long offset) {
        Set<Long> block_offsets = new HashSet<>();
//          System.out.println("Read block with offset: " + offset);
        try {
            randomAccessFile.seek(offset);
            // read block size
            long block_size = readNextVarInt(randomAccessFile);
//            System.out.println("Read block size: " + block_size);


            if (block_size < 1) {
                System.out.println("Invalid block size: " + block_size);
                return new HashSet<>();
            } else {
                blocks.put(offset, block_size);
            }

            // read block pointers
            block_offsets = readPointers(randomAccessFile, block_size);

        } catch (IOException e) {
            e.printStackTrace();
        }
        return block_offsets;
    }


    public static Set<Long> readPointers(RandomAccessFile raFile, long block_size) {
        long value = 0;
        int shift = 0;

        Set<Long> block_offsets = new HashSet<>();

        // Calculate size of VarInt size
        int size_block_size = 1;
        long max_block_size = 0x7f;
        while (block_size > max_block_size) {
            max_block_size |= 0x7F << (size_block_size * 7);
            size_block_size++;
        }

        byte[] data = new byte[(int) block_size - size_block_size];
        try {
            raFile.read(data, 0, (int) block_size - size_block_size);

            for (int i = 0; i < block_size - size_block_size && data[i] != 0; i++) {
                value |= (data[i] & 0x7F) << shift;
                if ((data[i] & 0x80) != 0) {
                    shift += 7;
                } else {
                    if (value > 0 && value < file_length && !offsets.contains(value))
                        block_offsets.add(value);
                    value = 0;
                    shift = 0;
                }
            }
            //        System.out.println(block_offsets);
            offsets.addAll(block_offsets);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return block_offsets;
    }

    public static long readNextVarInt(RandomAccessFile raFile) {
        long value = 0;
        byte data;
        int shift = 0;
        try {
            while ((data = (byte) raFile.read()) != -1) {
                value |= (data & 0x7F) << shift;
                if ((data & 0x80) != 0) {
                    shift += 7;
                } else {
                    break;
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        return value;
    }

}