/* fblocks - a program for printing out the block list of files
 * Copyright (C) 2003 Silicon Graphics, Inc.
 *
 * written by Andrew Clausen <clausen@gnu.org>
 *
 * This program is free software.  It may be modified and/or distributed
 * under the terms of the GNU General Public Licence version 2 or later,
 * as published by the Free Software Foundation, Inc.  There is NO WARRANTY.
 *
 * You can get this file from http://members.optusnet.com.au/clausen/sgi
 */

#include <fcntl.h>
#include <sys/ioctl.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <linux/fs.h>

int
div_round_up(int a, int b)
{
	return (a + b - 1) / b;
}

int
log2(int a)
{
	int result;
	for (result = 0; 1 << result <= a; result++)
		;
	return result - 1;
}

int
map_block(int fd, int blk)
{
	off_t arg = blk;
	if (ioctl(fd, FIBMAP, &arg)) {
		perror("fblocks");
		exit(1);
	}
	return arg;
}

int
get_run(int fd, int blk, int size, int* start, int* len)
{
	/* skip holes */
	while (!map_block(fd, blk) && blk < size)
		blk++;

	*start = map_block(fd, blk);
	if (!*start || blk == size)
		return 0;

	for (*len = 1; *len < size - blk; (*len)++) {
		if (map_block(fd, blk + *len) != *start + *len)
			break;
	}

	return 1;
}

void
print_block_list(int fd, int size)
{
	int blk, start, len;
	for (blk = 0; blk < size; blk += len) {
		if (get_run(fd, blk, size, &start, &len)) {
			if (len > 1)
				printf("%d+%d\n", start, len);
			else
				printf("%d\n", start);
		}
	}
}

/* TODO: try reading back and diff-ing? */
int
guess_blk_size(int fd)
{
	int i;
	struct stat st;
	int blk_size_approx, blk_size_big, blk_size_small;

	fstat(fd, &st);

	if (st.st_size < 8192) {
		printf("File too small to guess the block size.  Pass it!\n");
		exit(1);
	}

	for (i = st.st_size / 512; !map_block(fd, i); i--)
       		;

	blk_size_approx = st.st_size / i;
	blk_size_big = 1 << (log2(blk_size_approx) + 1);
	blk_size_small = 1 << log2(blk_size_approx);
	if (abs(blk_size_approx - blk_size_big)
			< abs(blk_size_approx - blk_size_small))
		return blk_size_big;
	else
		return blk_size_small;
}

int
get_size(int fd, int blk_size)
{
	struct stat st;
	fstat(fd, &st);
	return div_round_up(st.st_size, blk_size);
}

int
main(int argc, char* argv[])
{
	int fd;
	int blk_size;

	if (argc < 2) {
		printf("usage: fblocks FILE [BLOCK-SIZE]\n");
		return 1;
	}

	fd = open(argv[1], O_RDONLY);
	if (fd < 0) {
		perror(argv[1]);
		return 1;
	}

	if (argc == 3)
		blk_size = atoi(argv[2]);
	else
		blk_size = guess_blk_size(fd);

	printf("block size (bytes): %d\n", blk_size);
	print_block_list(fd, get_size(fd, blk_size));

	close(fd);
	return 0;
}