/* squash4.c - SquashFS */
/*
 *  GRUB  --  GRand Unified Bootloader
 *  Copyright (C) 2010  Free Software Foundation, Inc.
 *
 *  GRUB is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  GRUB is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <grub/err.h>
#include <grub/file.h>
#include <grub/mm.h>
#include <grub/misc.h>
#include <grub/disk.h>
#include <grub/types.h>
#include <grub/fshelp.h>
#include <grub/deflate.h>
#include <grub/safemath.h>

#define MINILZO_HAVE_CONFIG_H
#include "../lib/minilzo/minilzo.h"

#include "../lib/xzembed/xz.h"
#include "../lib/xzembed/xz_stream.h"

#include "../lib/lz4/lz4.h"

#define ZSTD_STATIC_LINKING_ONLY
#include "../lib/zstd/zstd.h"

GRUB_MOD_LICENSE("GPLv3+");

/*
  object         format      Pointed by
  superblock     RAW         Fixed offset (0)
  data           RAW ?       Fixed offset (60)
  inode table    Chunk       superblock
  dir table      Chunk       superblock
  fragment table Chunk       unk1
  unk1           RAW, Chunk  superblock
  unk2           RAW         superblock
  UID/GID        Chunk       exttblptr
  exttblptr      RAW         superblock

  UID/GID table is the array ot uint32_t
  unk1 contains pointer to fragment table followed by some chunk.
  unk2 containts one uint64_t
*/

GRUB_PACKED_START
struct grub_squash_super
{
	grub_uint32_t magic;
#define SQUASH_MAGIC 0x73717368
	grub_uint32_t dummy1;
	grub_uint32_t creation_time;
	grub_uint32_t block_size;
	grub_uint32_t dummy2;
	grub_uint16_t compression;
	grub_uint16_t dummy3;
	grub_uint64_t dummy4;
	grub_uint16_t root_ino_offset;
	grub_uint32_t root_ino_chunk;
	grub_uint16_t dummy5;
	grub_uint64_t total_size;
	grub_uint64_t exttbloffset;
	grub_uint64_t dummy6;
	grub_uint64_t inodeoffset;
	grub_uint64_t diroffset;
	grub_uint64_t unk1offset;
	grub_uint64_t unk2offset;
};
GRUB_PACKED_END

/* Chunk-based */
GRUB_PACKED_START
struct grub_squash_inode
{
	/* Same values as direlem types. */
	grub_uint16_t type;
	grub_uint16_t dummy[3];
	grub_uint32_t mtime;
	grub_uint32_t dummy2;
	union
	{
		struct
		{
			grub_uint32_t chunk;
			grub_uint32_t fragment;
			grub_uint32_t offset;
			grub_uint32_t size;
			grub_uint32_t block_size[1];
		} file;
		struct
		{
			grub_uint64_t chunk;
			grub_uint64_t size;
			grub_uint32_t dummy1[3];
			grub_uint32_t fragment;
			grub_uint32_t offset;
			grub_uint32_t dummy3;
			grub_uint32_t block_size[1];
		} long_file;
		struct
		{
			grub_uint32_t chunk;
			grub_uint32_t dummy;
			grub_uint16_t size;
			grub_uint16_t offset;
		} dir;
		struct
		{
			grub_uint32_t dummy1;
			grub_uint32_t size;
			grub_uint32_t chunk;
			grub_uint32_t dummy2;
			grub_uint16_t dummy3;
			grub_uint16_t offset;
		} long_dir;
		struct
		{
			grub_uint32_t dummy;
			grub_uint32_t namelen;
			char name[1];
		} symlink;
	};
};
GRUB_PACKED_END

struct grub_squash_cache_inode
{
	struct grub_squash_inode ino;
	grub_disk_addr_t ino_chunk;
	grub_uint16_t	ino_offset;
	grub_uint32_t* block_sizes;
	grub_disk_addr_t* cumulated_block_sizes;
};

/* Chunk-based.  */
GRUB_PACKED_START
struct grub_squash_dirent_header
{
	/* Actually the value is the number of elements - 1.  */
	grub_uint32_t nelems;
	grub_uint32_t ino_chunk;
	grub_uint32_t dummy;
};
GRUB_PACKED_END

GRUB_PACKED_START
struct grub_squash_dirent
{
	grub_uint16_t ino_offset;
	grub_uint16_t dummy;
	grub_uint16_t type;
	/* Actually the value is the length of name - 1.  */
	grub_uint16_t namelen;
	char name[0];
};
GRUB_PACKED_END

enum
{
	SQUASH_TYPE_DIR = 1,
	SQUASH_TYPE_REGULAR = 2,
	SQUASH_TYPE_SYMLINK = 3,
	SQUASH_TYPE_LONG_DIR = 8,
	SQUASH_TYPE_LONG_REGULAR = 9,
};

GRUB_PACKED_START
struct grub_squash_frag_desc
{
	grub_uint64_t offset;
	grub_uint32_t size;
	grub_uint32_t dummy;
};
GRUB_PACKED_END

enum
{
	SQUASH_CHUNK_FLAGS = 0x8000,
	SQUASH_CHUNK_UNCOMPRESSED = 0x8000
};

enum
{
	SQUASH_BLOCK_FLAGS = 0x1000000,
	SQUASH_BLOCK_UNCOMPRESSED = 0x1000000
};

enum
{
	COMPRESSION_ZLIB = 1,
	COMPRESSION_LZMA = 2, // lzma1
	COMPRESSION_LZO = 3,
	COMPRESSION_XZ = 4, // lzma2
	COMPRESSION_LZ4 = 5,
	COMPRESSION_ZSTD = 6,
};

#define SQUASH_CHUNK_SIZE 0x2000
#define XZBUFSIZ 0x2000

struct grub_squash_data
{
	grub_disk_t disk;
	struct grub_squash_super sb;
	struct grub_squash_cache_inode ino;
	grub_uint64_t fragments;
	int log2_blksz;
	grub_size_t blksz;
	grub_ssize_t(*decompress) (char* inbuf, grub_size_t insize, grub_off_t off,
		char* outbuf, grub_size_t outsize,
		struct grub_squash_data* data);
	struct xz_dec* xzdec;
	char* xzbuf;
};

struct grub_fshelp_node
{
	struct grub_squash_data* data;
	struct grub_squash_inode ino;
	grub_size_t stsize;
	struct
	{
		grub_disk_addr_t ino_chunk;
		grub_uint16_t ino_offset;
	} stack[1];
};

static grub_err_t
read_chunk(struct grub_squash_data* data, void* buf, grub_size_t len,
	grub_uint64_t chunk_start, grub_off_t offset)
{
	while (len > 0)
	{
		grub_uint64_t csize;
		grub_uint16_t d;
		grub_err_t err;
		while (1)
		{
			err = grub_disk_read(data->disk,
				chunk_start >> GRUB_DISK_SECTOR_BITS,
				chunk_start & (GRUB_DISK_SECTOR_SIZE - 1),
				sizeof(d), &d);
			if (err)
				return err;
			if (offset < SQUASH_CHUNK_SIZE)
				break;
			offset -= SQUASH_CHUNK_SIZE;
			chunk_start += 2 + (grub_le_to_cpu16(d) & ~SQUASH_CHUNK_FLAGS);
		}

		csize = SQUASH_CHUNK_SIZE - offset;
		if (csize > len)
			csize = len;

		if (grub_le_to_cpu16(d) & SQUASH_CHUNK_UNCOMPRESSED)
		{
			grub_disk_addr_t a = chunk_start + 2 + offset;
			err = grub_disk_read(data->disk, (a >> GRUB_DISK_SECTOR_BITS),
				a & (GRUB_DISK_SECTOR_SIZE - 1),
				csize, buf);
			if (err)
				return err;
		}
		else
		{
			char* tmp;
			grub_size_t bsize = grub_le_to_cpu16(d) & ~SQUASH_CHUNK_FLAGS;
			grub_disk_addr_t a = chunk_start + 2;
			tmp = grub_malloc(bsize);
			if (!tmp)
				return grub_errno;
			/* FIXME: buffer uncompressed data.  */
			err = grub_disk_read(data->disk, (a >> GRUB_DISK_SECTOR_BITS),
				a & (GRUB_DISK_SECTOR_SIZE - 1),
				bsize, tmp);
			if (err)
			{
				grub_free(tmp);
				return err;
			}

			if (data->decompress(tmp, bsize, offset,
				buf, csize, data) < 0)
			{
				grub_free(tmp);
				return grub_errno;
			}
			grub_free(tmp);
		}
		len -= csize;
		offset += csize;
		buf = (char*)buf + csize;
	}
	return GRUB_ERR_NONE;
}

static grub_ssize_t
zlib_decompress(char* inbuf, grub_size_t insize, grub_off_t off,
	char* outbuf, grub_size_t outsize,
	struct grub_squash_data* data __attribute__((unused)))
{
	return grub_zlib_decompress(inbuf, insize, off, outbuf, outsize);
}

static grub_ssize_t
lzo_decompress(char* inbuf, grub_size_t insize, grub_off_t off,
	char* outbuf, grub_size_t len, struct grub_squash_data* data)
{
	lzo_uint usize = data->blksz;
	grub_uint8_t* udata;

	if (usize < 8192)
		usize = 8192;

	udata = grub_malloc(usize);
	if (!udata)
		return -1;

	if (lzo1x_decompress_safe((grub_uint8_t*)inbuf,
		insize, udata, &usize, NULL) != LZO_E_OK)
	{
		grub_error(GRUB_ERR_BAD_FS, "incorrect compressed chunk");
		grub_free(udata);
		return -1;
	}
	grub_memcpy(outbuf, udata + off, len);
	grub_free(udata);
	return len;
}

static grub_ssize_t
xz_decompress(char* inbuf, grub_size_t insize, grub_off_t off,
	char* outbuf, grub_size_t len, struct grub_squash_data* data)
{
	grub_size_t ret = 0;
	grub_off_t pos = 0;
	struct xz_buf buf;

	xz_dec_reset(data->xzdec);
	buf.in = (grub_uint8_t*)inbuf;
	buf.in_pos = 0;
	buf.in_size = insize;
	buf.out = (grub_uint8_t*)data->xzbuf;
	buf.out_pos = 0;
	buf.out_size = XZBUFSIZ;

	while (len)
	{
		enum xz_ret xzret;

		buf.out_pos = 0;

		xzret = xz_dec_run(data->xzdec, &buf);

		if (xzret != XZ_OK && xzret != XZ_STREAM_END)
		{
			grub_error(GRUB_ERR_BAD_COMPRESSED_DATA, "invalid xz chunk");
			return -1;
		}
		if (pos + buf.out_pos >= off)
		{
			grub_ssize_t outoff = pos - off;
			grub_size_t l;
			if (outoff >= 0)
			{
				l = buf.out_pos;
				if (l > len)
					l = len;
				grub_memcpy(outbuf + outoff, buf.out, l);
			}
			else
			{
				outoff = -outoff;
				l = buf.out_pos - outoff;
				if (l > len)
					l = len;
				grub_memcpy(outbuf, buf.out + outoff, l);
			}
			ret += l;
			len -= l;
		}
		pos += buf.out_pos;
		if (xzret == XZ_STREAM_END)
			break;
	}
	return ret;
}

static grub_ssize_t
lz4_decompress(char* inbuf, grub_size_t insize, grub_off_t off,
	char* outbuf, grub_size_t len, struct grub_squash_data* data)
{
	(void)data;
	int res;
	size_t usize = len + off;
	char* udata;
	if (usize < 0x400000)
		usize = 0x400000;
	udata = grub_malloc(usize);
	if (!udata)
		return -1;

	res = LZ4_decompress_safe(inbuf, udata, insize, (int)usize);

	if (res < 0)
	{
		grub_error(GRUB_ERR_BAD_FS, "incorrect compressed chunk");
		grub_free(udata);
		return -1;
	}
	grub_memcpy(outbuf, udata + off, len);
	grub_free(udata);
	return len;
}

static grub_ssize_t
zstd_decompress(char* inbuf, grub_size_t insize, grub_off_t off,
	char* outbuf, grub_size_t len, struct grub_squash_data* data)
{
	(void)data;
	size_t res;
	size_t usize = len + off;
	grub_uint8_t* udata;

	if (usize < 0x20000)
		usize = 0x20000;
	udata = grub_malloc(usize);
	if (!udata)
		return -1;

	res = ZSTD_decompress(udata, usize, inbuf, insize);

	if (ZSTD_isError(res))
	{
		grub_error(GRUB_ERR_BAD_FS, "incorrect compressed chunk");
		grub_free(udata);
		return -1;
	}
	grub_memcpy(outbuf, udata + off, len);
	grub_free(udata);
	return len;
}

static struct grub_squash_data*
squash_mount(grub_disk_t disk)
{
	struct grub_squash_super sb;
	grub_err_t err;
	struct grub_squash_data* data;
	grub_uint64_t frag;

	err = grub_disk_read(disk, 0, 0, sizeof(sb), &sb);
	if (grub_errno == GRUB_ERR_OUT_OF_RANGE)
		grub_error(GRUB_ERR_BAD_FS, "not a squash4");
	if (err)
		return NULL;
	if (sb.magic != grub_cpu_to_le32_compile_time(SQUASH_MAGIC)
		|| sb.block_size == 0
		|| ((sb.block_size - 1) & sb.block_size))
	{
		grub_error(GRUB_ERR_BAD_FS, "not squash4");
		return NULL;
	}

	err = grub_disk_read(disk,
		grub_le_to_cpu64(sb.unk1offset)
		>> GRUB_DISK_SECTOR_BITS,
		grub_le_to_cpu64(sb.unk1offset)
		& (GRUB_DISK_SECTOR_SIZE - 1), sizeof(frag), &frag);
	if (grub_errno == GRUB_ERR_OUT_OF_RANGE)
		grub_error(GRUB_ERR_BAD_FS, "not a squash4");
	if (err)
		return NULL;

	data = grub_zalloc(sizeof(*data));
	if (!data)
		return NULL;
	data->sb = sb;
	data->disk = disk;
	data->fragments = grub_le_to_cpu64(frag);

	switch (sb.compression)
	{
	case grub_cpu_to_le16_compile_time(COMPRESSION_ZLIB):
		data->decompress = zlib_decompress;
		break;
	case grub_cpu_to_le16_compile_time(COMPRESSION_LZO):
		data->decompress = lzo_decompress;
		break;
	case grub_cpu_to_le16_compile_time(COMPRESSION_XZ):
		data->decompress = xz_decompress;
		data->xzbuf = grub_malloc(XZBUFSIZ);
		if (!data->xzbuf)
		{
			grub_free(data);
			return NULL;
		}
		data->xzdec = xz_dec_init(1 << 16);
		if (!data->xzdec)
		{
			grub_free(data->xzbuf);
			grub_free(data);
			return NULL;
		}
		break;
	case grub_cpu_to_le16_compile_time(COMPRESSION_LZ4):
		data->decompress = lz4_decompress;
		break;
	case grub_cpu_to_le16_compile_time(COMPRESSION_ZSTD):
		data->decompress = zstd_decompress;
		break;
	default:
		grub_free(data);
		grub_error(GRUB_ERR_BAD_FS, "unsupported compression %d",
			grub_le_to_cpu16(sb.compression));
		return NULL;
	}

	data->blksz = grub_le_to_cpu32(data->sb.block_size);
	for (data->log2_blksz = 0;
		(1U << data->log2_blksz) < data->blksz;
		data->log2_blksz++);

	return data;
}

static char*
grub_squash_read_symlink(grub_fshelp_node_t node)
{
	char* ret;
	grub_err_t err;
	grub_size_t sz;

	if (grub_add(grub_le_to_cpu32(node->ino.symlink.namelen), 1, &sz))
	{
		grub_error(GRUB_ERR_OUT_OF_RANGE, N_("overflow is detected"));
		return NULL;
	}

	ret = grub_malloc(sz);
	if (!ret)
		return NULL;

	err = read_chunk(node->data, ret,
		grub_le_to_cpu32(node->ino.symlink.namelen),
		grub_le_to_cpu64(node->data->sb.inodeoffset)
		+ node->stack[node->stsize - 1].ino_chunk,
		node->stack[node->stsize - 1].ino_offset
		+ (node->ino.symlink.name - (char*)&node->ino));
	if (err)
	{
		grub_free(ret);
		return NULL;
	}
	ret[grub_le_to_cpu32(node->ino.symlink.namelen)] = 0;
	return ret;
}

static int
grub_squash_iterate_dir(grub_fshelp_node_t dir,
	grub_fshelp_iterate_dir_hook_t hook, void* hook_data)
{
	grub_uint32_t off;
	grub_uint32_t endoff;
	grub_uint64_t chunk;
	unsigned i;

	/* FIXME: why - 3 ? */
	switch (dir->ino.type)
	{
	case grub_cpu_to_le16_compile_time(SQUASH_TYPE_DIR):
		off = grub_le_to_cpu16(dir->ino.dir.offset);
		endoff = grub_le_to_cpu16(dir->ino.dir.size) + off - 3;
		chunk = grub_le_to_cpu32(dir->ino.dir.chunk);
		break;
	case grub_cpu_to_le16_compile_time(SQUASH_TYPE_LONG_DIR):
		off = grub_le_to_cpu16(dir->ino.long_dir.offset);
		endoff = grub_le_to_cpu16(dir->ino.long_dir.size) + off - 3;
		chunk = grub_le_to_cpu32(dir->ino.long_dir.chunk);
		break;
	default:
		grub_error(GRUB_ERR_BAD_FS, "unexpected ino type 0x%x",
			grub_le_to_cpu16(dir->ino.type));
		return 0;
	}

	{
		grub_fshelp_node_t node;
		grub_size_t sz;

		if (grub_mul(dir->stsize, sizeof(dir->stack[0]), &sz) ||
			grub_add(sz, sizeof(*node), &sz))
			return 0;

		node = grub_malloc(sz);
		if (!node)
			return 0;
		grub_memcpy(node, dir, sz);
		if (hook(".", GRUB_FSHELP_DIR, node, hook_data))
			return 1;

		if (dir->stsize != 1)
		{
			grub_err_t err;

			if (grub_mul(dir->stsize, sizeof(dir->stack[0]), &sz) ||
				grub_add(sz, sizeof(*node), &sz))
				return 0;

			node = grub_malloc(sz);
			if (!node)
				return 0;

			grub_memcpy(node, dir, sz);

			node->stsize--;
			err = read_chunk(dir->data, &node->ino, sizeof(node->ino),
				grub_le_to_cpu64(dir->data->sb.inodeoffset)
				+ node->stack[node->stsize - 1].ino_chunk,
				node->stack[node->stsize - 1].ino_offset);
			if (err)
			{
				grub_free(node);
				return 0;
			}

			if (hook("..", GRUB_FSHELP_DIR, node, hook_data))
				return 1;
		}
	}

	while (off < endoff)
	{
		struct grub_squash_dirent_header dh;
		grub_err_t err;

		err = read_chunk(dir->data, &dh, sizeof(dh),
			grub_le_to_cpu64(dir->data->sb.diroffset)
			+ chunk, off);
		if (err)
			return 0;
		off += sizeof(dh);
		for (i = 0; i < (unsigned)grub_le_to_cpu32(dh.nelems) + 1; i++)
		{
			char* buf;
			int r;
			struct grub_fshelp_node* node;
			enum grub_fshelp_filetype filetype = GRUB_FSHELP_REG;
			struct grub_squash_dirent di;
			struct grub_squash_inode ino;
			grub_size_t sz;

			err = read_chunk(dir->data, &di, sizeof(di),
				grub_le_to_cpu64(dir->data->sb.diroffset)
				+ chunk, off);
			if (err)
				return 0;
			off += sizeof(di);

			err = read_chunk(dir->data, &ino, sizeof(ino),
				grub_le_to_cpu64(dir->data->sb.inodeoffset)
				+ grub_le_to_cpu32(dh.ino_chunk),
				grub_cpu_to_le16(di.ino_offset));
			if (err)
				return 0;

			buf = grub_malloc(grub_le_to_cpu16(di.namelen) + 2);
			if (!buf)
				return 0;
			err = read_chunk(dir->data, buf,
				grub_le_to_cpu16(di.namelen) + 1,
				grub_le_to_cpu64(dir->data->sb.diroffset)
				+ chunk, off);
			if (err)
			{
				grub_free(buf);
				return 0;
			}

			off += grub_le_to_cpu16(di.namelen) + 1;
			buf[grub_le_to_cpu16(di.namelen) + 1] = 0;
			if (grub_le_to_cpu16(di.type) == SQUASH_TYPE_DIR)
				filetype = GRUB_FSHELP_DIR;
			if (grub_le_to_cpu16(di.type) == SQUASH_TYPE_SYMLINK)
				filetype = GRUB_FSHELP_SYMLINK;

			if (grub_add(dir->stsize, 1, &sz) ||
				grub_mul(sz, sizeof(dir->stack[0]), &sz) ||
				grub_add(sz, sizeof(*node), &sz))
			{
				grub_free(buf);
				return 0;
			}

			node = grub_malloc(sz);
			if (!node)
			{
				grub_free(buf);
				return 0;
			}

			grub_memcpy(node, dir, sz - sizeof(dir->stack[0]));

			node->ino = ino;
			node->stack[node->stsize].ino_chunk = grub_le_to_cpu32(dh.ino_chunk);
			node->stack[node->stsize].ino_offset = grub_le_to_cpu16(di.ino_offset);
			node->stsize++;
			r = hook(buf, filetype, node, hook_data);

			grub_free(buf);
			if (r)
				return r;
		}
	}
	return 0;
}

static grub_err_t
make_root_node(struct grub_squash_data* data, struct grub_fshelp_node* root)
{
	grub_memset(root, 0, sizeof(*root));
	root->data = data;
	root->stsize = 1;
	root->stack[0].ino_chunk = grub_le_to_cpu32(data->sb.root_ino_chunk);
	root->stack[0].ino_offset = grub_cpu_to_le16(data->sb.root_ino_offset);
	return read_chunk(data, &root->ino, sizeof(root->ino),
		grub_le_to_cpu64(data->sb.inodeoffset)
		+ root->stack[0].ino_chunk,
		root->stack[0].ino_offset);
}

static void
squash_unmount(struct grub_squash_data* data)
{
	if (data->xzdec)
		xz_dec_end(data->xzdec);
	grub_free(data->xzbuf);
	grub_free(data->ino.cumulated_block_sizes);
	grub_free(data->ino.block_sizes);
	grub_free(data);
}


/* Context for grub_squash_dir.  */
struct grub_squash_dir_ctx
{
	grub_fs_dir_hook_t hook;
	void* hook_data;
};

/* Helper for grub_squash_dir.  */
static int
grub_squash_dir_iter(const char* filename, enum grub_fshelp_filetype filetype,
	grub_fshelp_node_t node, void* data)
{
	struct grub_squash_dir_ctx* ctx = data;
	struct grub_dirhook_info info;

	grub_memset(&info, 0, sizeof(info));
	info.dir = ((filetype & GRUB_FSHELP_TYPE_MASK) == GRUB_FSHELP_DIR);
	info.symlink = ((filetype & GRUB_FSHELP_TYPE_MASK) == GRUB_FSHELP_SYMLINK);
	info.mtimeset = 1;
	info.mtime = grub_le_to_cpu32(node->ino.mtime);
	grub_free(node);
	return ctx->hook(filename, &info, ctx->hook_data);
}

static grub_err_t
grub_squash_dir(grub_disk_t disk, const char* path,
	grub_fs_dir_hook_t hook, void* hook_data)
{
	struct grub_squash_dir_ctx ctx = { hook, hook_data };
	struct grub_squash_data* data = 0;
	struct grub_fshelp_node* fdiro = 0;
	struct grub_fshelp_node root;
	grub_err_t err;

	data = squash_mount(disk);
	if (!data)
		return grub_errno;

	err = make_root_node(data, &root);
	if (err)
		return err;

	grub_fshelp_find_file(path, &root, &fdiro, grub_squash_iterate_dir,
		grub_squash_read_symlink, GRUB_FSHELP_DIR);
	if (!grub_errno)
		grub_squash_iterate_dir(fdiro, grub_squash_dir_iter, &ctx);

	squash_unmount(data);

	return grub_errno;
}

static grub_err_t
grub_squash_open(struct grub_file* file, const char* name)
{
	struct grub_squash_data* data = 0;
	struct grub_fshelp_node* fdiro = 0;
	struct grub_fshelp_node root;
	grub_err_t err;

	data = squash_mount(file->disk);
	if (!data)
		return grub_errno;

	err = make_root_node(data, &root);
	if (err)
		return err;

	grub_fshelp_find_file(name, &root, &fdiro, grub_squash_iterate_dir,
		grub_squash_read_symlink, GRUB_FSHELP_REG);
	if (grub_errno)
	{
		squash_unmount(data);
		return grub_errno;
	}

	file->data = data;
	data->ino.ino = fdiro->ino;
	data->ino.block_sizes = NULL;
	data->ino.cumulated_block_sizes = NULL;
	data->ino.ino_chunk = fdiro->stack[fdiro->stsize - 1].ino_chunk;
	data->ino.ino_offset = fdiro->stack[fdiro->stsize - 1].ino_offset;

	switch (fdiro->ino.type)
	{
	case grub_cpu_to_le16_compile_time(SQUASH_TYPE_LONG_REGULAR):
		file->size = grub_le_to_cpu64(fdiro->ino.long_file.size);
		break;
	case grub_cpu_to_le16_compile_time(SQUASH_TYPE_REGULAR):
		file->size = grub_le_to_cpu32(fdiro->ino.file.size);
		break;
	default:
	{
		grub_uint16_t type = grub_le_to_cpu16(fdiro->ino.type);
		grub_free(fdiro);
		squash_unmount(data);
		return grub_error(GRUB_ERR_BAD_FS, "unexpected ino type 0x%x", type);
	}
	}

	grub_free(fdiro);

	return GRUB_ERR_NONE;
}

static grub_ssize_t
direct_read(struct grub_squash_data* data,
	struct grub_squash_cache_inode* ino,
	grub_off_t off, char* buf, grub_size_t len)
{
	grub_err_t err = GRUB_ERR_NONE;
	grub_off_t cumulated_uncompressed_size = 0;
	grub_uint64_t a = 0;
	grub_size_t i;
	grub_size_t origlen = len;

	switch (ino->ino.type)
	{
	case grub_cpu_to_le16_compile_time(SQUASH_TYPE_LONG_REGULAR):
		a = grub_le_to_cpu64(ino->ino.long_file.chunk);
		break;
	case grub_cpu_to_le16_compile_time(SQUASH_TYPE_REGULAR):
		a = grub_le_to_cpu32(ino->ino.file.chunk);
		break;
	}

	if (!ino->block_sizes)
	{
		grub_off_t total_size = 0;
		grub_size_t total_blocks;
		grub_size_t block_offset = 0;
		switch (ino->ino.type)
		{
		case grub_cpu_to_le16_compile_time(SQUASH_TYPE_LONG_REGULAR):
			total_size = grub_le_to_cpu64(ino->ino.long_file.size);
			block_offset = ((char*)&ino->ino.long_file.block_size
				- (char*)&ino->ino);
			break;
		case grub_cpu_to_le16_compile_time(SQUASH_TYPE_REGULAR):
			total_size = grub_le_to_cpu32(ino->ino.file.size);
			block_offset = ((char*)&ino->ino.file.block_size
				- (char*)&ino->ino);
			break;
		}
		total_blocks = ((total_size + data->blksz - 1) >> data->log2_blksz);
		ino->block_sizes = grub_malloc(total_blocks
			* sizeof(ino->block_sizes[0]));
		ino->cumulated_block_sizes = grub_malloc(total_blocks
			* sizeof(ino->cumulated_block_sizes[0]));
		if (!ino->block_sizes || !ino->cumulated_block_sizes)
		{
			grub_free(ino->block_sizes);
			grub_free(ino->cumulated_block_sizes);
			ino->block_sizes = 0;
			ino->cumulated_block_sizes = 0;
			return -1;
		}
		err = read_chunk(data, ino->block_sizes,
			total_blocks * sizeof(ino->block_sizes[0]),
			grub_le_to_cpu64(data->sb.inodeoffset)
			+ ino->ino_chunk,
			ino->ino_offset + block_offset);
		if (err)
		{
			grub_free(ino->block_sizes);
			grub_free(ino->cumulated_block_sizes);
			ino->block_sizes = 0;
			ino->cumulated_block_sizes = 0;
			return -1;
		}
		ino->cumulated_block_sizes[0] = 0;
		for (i = 1; i < total_blocks; i++)
			ino->cumulated_block_sizes[i] = ino->cumulated_block_sizes[i - 1]
			+ (grub_le_to_cpu32(ino->block_sizes[i - 1]) & ~SQUASH_BLOCK_FLAGS);
	}

	if (a == 0)
		a = sizeof(struct grub_squash_super);
	i = off >> data->log2_blksz;
	cumulated_uncompressed_size = data->blksz * (grub_disk_addr_t)i;
	while (cumulated_uncompressed_size < off + len)
	{
		grub_size_t boff, curread;
		boff = off - cumulated_uncompressed_size;
		curread = data->blksz - boff;
		if (curread > len)
			curread = len;
		if (!ino->block_sizes[i])
		{
			/* Sparse block */
			grub_memset(buf, '\0', curread);
		}
		else if (!(ino->block_sizes[i]
			& grub_cpu_to_le32_compile_time(SQUASH_BLOCK_UNCOMPRESSED)))
		{
			char* block;
			grub_size_t csize;
			csize = grub_le_to_cpu32(ino->block_sizes[i]) & ~SQUASH_BLOCK_FLAGS;
			block = grub_malloc(csize);
			if (!block)
				return -1;
			err = grub_disk_read(data->disk,
				(ino->cumulated_block_sizes[i] + a)
				>> GRUB_DISK_SECTOR_BITS,
				(ino->cumulated_block_sizes[i] + a)
				& (GRUB_DISK_SECTOR_SIZE - 1),
				csize, block);
			if (err)
			{
				grub_free(block);
				return -1;
			}
			if (data->decompress(block, csize, boff, buf, curread, data)
				!= (grub_ssize_t)curread)
			{
				grub_free(block);
				if (!grub_errno)
					grub_error(GRUB_ERR_BAD_FS, "incorrect compressed chunk");
				return -1;
			}
			grub_free(block);
		}
		else
			err = grub_disk_read(data->disk,
				(ino->cumulated_block_sizes[i] + a + boff)
				>> GRUB_DISK_SECTOR_BITS,
				(ino->cumulated_block_sizes[i] + a + boff)
				& (GRUB_DISK_SECTOR_SIZE - 1),
				curread, buf);
		if (err)
			return -1;
		off += curread;
		len -= curread;
		buf += curread;
		cumulated_uncompressed_size += grub_le_to_cpu32(data->sb.block_size);
		i++;
	}
	return origlen;
}

static grub_ssize_t
grub_squash_read(grub_file_t file, char* buf, grub_size_t len)
{
	struct grub_squash_data* data = file->data;
	struct grub_squash_cache_inode* ino = &data->ino;
	grub_off_t off = file->offset;
	grub_err_t err;
	grub_uint64_t a, b;
	grub_uint32_t fragment = 0;
	int compressed = 0;
	struct grub_squash_frag_desc frag;
	grub_off_t direct_len;
	grub_uint64_t mask = grub_le_to_cpu32(data->sb.block_size) - 1;
	grub_size_t orig_len = len;

	switch (ino->ino.type)
	{
	case grub_cpu_to_le16_compile_time(SQUASH_TYPE_LONG_REGULAR):
		fragment = grub_le_to_cpu32(ino->ino.long_file.fragment);
		break;
	case grub_cpu_to_le16_compile_time(SQUASH_TYPE_REGULAR):
		fragment = grub_le_to_cpu32(ino->ino.file.fragment);
		break;
	}

	/* Squash may pack file tail as fragment. So read initial part directly and
	   get tail from fragments */
	direct_len = fragment == 0xffffffff ? file->size : file->size & ~mask;
	if (off < direct_len)
	{
		grub_size_t read_len = direct_len - off;
		grub_ssize_t res;

		if (read_len > len)
			read_len = len;
		res = direct_read(data, ino, off, buf, read_len);
		if ((grub_size_t)res != read_len)
			return -1; /* FIXME: is short read possible here? */
		len -= read_len;
		if (!len)
			return read_len;
		buf += read_len;
		off = 0;
	}
	else
		off -= direct_len;

	err = read_chunk(data, &frag, sizeof(frag),
		data->fragments, sizeof(frag) * fragment);
	if (err)
		return -1;
	a = grub_le_to_cpu64(frag.offset);
	compressed = !(frag.size & grub_cpu_to_le32_compile_time(SQUASH_BLOCK_UNCOMPRESSED));
	if (ino->ino.type == grub_cpu_to_le16_compile_time(SQUASH_TYPE_LONG_REGULAR))
		b = grub_le_to_cpu32(ino->ino.long_file.offset) + off;
	else
		b = grub_le_to_cpu32(ino->ino.file.offset) + off;

	/* FIXME: cache uncompressed chunks.  */
	if (compressed)
	{
		char* block;
		block = grub_malloc(grub_le_to_cpu32(frag.size));
		if (!block)
			return -1;
		err = grub_disk_read(data->disk,
			a >> GRUB_DISK_SECTOR_BITS,
			a & (GRUB_DISK_SECTOR_SIZE - 1),
			grub_le_to_cpu32(frag.size), block);
		if (err)
		{
			grub_free(block);
			return -1;
		}
		if (data->decompress(block, grub_le_to_cpu32(frag.size),
			b, buf, len, data)
			!= (grub_ssize_t)len)
		{
			grub_free(block);
			if (!grub_errno)
				grub_error(GRUB_ERR_BAD_FS, "incorrect compressed chunk");
			return -1;
		}
		grub_free(block);
	}
	else
	{
		err = grub_disk_read(data->disk, (a + b) >> GRUB_DISK_SECTOR_BITS,
			(a + b) & (GRUB_DISK_SECTOR_SIZE - 1), len, buf);
		if (err)
			return -1;
	}
	return orig_len;
}

static grub_err_t
grub_squash_close(grub_file_t file)
{
	squash_unmount(file->data);
	return GRUB_ERR_NONE;
}

static grub_err_t
grub_squash_mtime(grub_disk_t disk, grub_int64_t* tm)
{
	struct grub_squash_data* data = 0;

	data = squash_mount(disk);
	if (!data)
		return grub_errno;
	*tm = grub_le_to_cpu32(data->sb.creation_time);
	squash_unmount(data);
	return GRUB_ERR_NONE;
}

static struct grub_fs grub_squash_fs =
{
	.name = "squash4",
	.fs_dir = grub_squash_dir,
	.fs_open = grub_squash_open,
	.fs_read = grub_squash_read,
	.fs_close = grub_squash_close,
	.fs_mtime = grub_squash_mtime,
	.next = 0
};

GRUB_MOD_INIT(squash4)
{
	grub_fs_register(&grub_squash_fs);
}

GRUB_MOD_FINI(squash4)
{
	grub_fs_unregister(&grub_squash_fs);
}
