#include "fitz-internal.h"
#include "mupdf-internal.h"

/* #define DEBUG_LINEARIZATION */
/* #define DEBUG_HEAP_SORT */
/* #define DEBUG_WRITING */


typedef struct pdf_write_options_s pdf_write_options;

/* As part of linearization, we need to keep a list of what objects are used
 * by what page. We do this by recording the objects used in a given page
 * in a page_objects structure. We have a list of these structures (one per
 * page) in the page_objects_list structure.
 *
 * The page_objects structure maintains a heap in the object array, so
 * insertion takes log n time, and we can heapsort and dedupe at the end for
 * a total worse case n log n time.
 *
 * The magic heap invariant is that:
 *   entry[n] >= entry[(n+1)*2-1] & entry[n] >= entry[(n+1)*2]
 * or equivalently:
 *   entry[(n-1)>>1] >= entry[n]
 *
 * For a discussion of the heap data structure (and heapsort) see Kingston,
 * "Algorithms and Data Structures".
 */
typedef struct {
	int num_shared;
	int page_object_number;
	int num_objects;
	int min_ofs;
	int max_ofs;
	/* Extensible list of objects used on this page */
	int cap;
	int len;
	int object[1];
} page_objects;

typedef struct {
	int cap;
	int len;
	page_objects *page[1];
} page_objects_list;

struct pdf_write_options_s
{
	FILE *out;
	int do_ascii;
	int do_expand;
	int do_garbage;
	int do_linear;
	int *use_list;
	int *ofs_list;
	int *gen_list;
	int *renumber_map;
	/* The following extras are required for linearization */
	int *rev_renumber_map;
	int *rev_gen_list;
	int start;
	int first_xref_offset;
	int main_xref_offset;
	int first_xref_entry_offset;
	int file_len;
	int hints_shared_offset;
	int hintstream_len;
	pdf_obj *linear_l;
	pdf_obj *linear_h0;
	pdf_obj *linear_h1;
	pdf_obj *linear_o;
	pdf_obj *linear_e;
	pdf_obj *linear_n;
	pdf_obj *linear_t;
	pdf_obj *hints_s;
	pdf_obj *hints_length;
	int page_count;
	page_objects_list *page_object_lists;
};

/*
 * Constants for use with use_list.
 *
 * If use_list[num] = 0, then object num is unused.
 * If use_list[num] & PARAMS, then object num is the linearisation params obj.
 * If use_list[num] & CATALOGUE, then object num is used by the catalogue.
 * If use_list[num] & PAGE1, then object num is used by page 1.
 * If use_list[num] & SHARED, then object num is shared between pages.
 * If use_list[num] & PAGE_OBJECT then this must be the first object in a page.
 * Otherwise object num is used by page (use_list[num]>>USE_PAGE_SHIFT).
 */
enum
{
	USE_CATALOGUE = 2,
	USE_PAGE1 = 4,
	USE_SHARED = 8,
	USE_PARAMS = 16,
	USE_HINTS = 32,
	USE_PAGE_OBJECT = 64,
	USE_PAGE_MASK = ~127,
	USE_PAGE_SHIFT = 7
};

/*
 * page_objects and page_object_list handling functions
 */
static page_objects_list *
page_objects_list_create(fz_context *ctx)
{
	page_objects_list *pol = fz_calloc(ctx, 1, sizeof(*pol));

	pol->cap = 1;
	pol->len = 0;
	return pol;
}

static void
page_objects_list_destroy(fz_context *ctx, page_objects_list *pol)
{
	int i;

	if (!pol)
		return;
	for (i = 0; i < pol->len; i++)
	{
		fz_free(ctx, pol->page[i]);
	}
	fz_free(ctx, pol);
}

static void
page_objects_list_ensure(fz_context *ctx, page_objects_list **pol, int newcap)
{
	int oldcap = (*pol)->cap;
	if (newcap <= oldcap)
		return;
	*pol = fz_resize_array(ctx, *pol, 1, sizeof(page_objects_list) + (newcap-1)*sizeof(page_objects *));
	memset(&(*pol)->page[oldcap], 0, (newcap-oldcap)*sizeof(page_objects *));
	(*pol)->cap = newcap;
}

static page_objects *
page_objects_create(fz_context *ctx)
{
	int initial_cap = 8;
	page_objects *po = fz_calloc(ctx, 1, sizeof(*po) + (initial_cap-1) * sizeof(int));

	po->cap = initial_cap;
	po->len = 0;
	return po;

}

static void
page_objects_insert(fz_context *ctx, page_objects **ppo, int i)
{
	page_objects *po;

	/* Make a page_objects if we don't have one */
	if (*ppo == NULL)
		*ppo = page_objects_create(ctx);

	po = *ppo;
	/* page_objects insertion: extend the page_objects by 1, and put us on the end */
	if (po->len == po->cap)
	{
		po = fz_resize_array(ctx, po, 1, sizeof(page_objects) + (po->cap*2 - 1)*sizeof(int));
		po->cap *= 2;
		*ppo = po;
	}
	po->object[po->len++] = i;
}

static void
page_objects_list_insert(fz_context *ctx, pdf_write_options *opts, int page, int object)
{
	page_objects_list_ensure(ctx, &opts->page_object_lists, page+1);
	if (opts->page_object_lists->len < page+1)
		opts->page_object_lists->len = page+1;
	page_objects_insert(ctx, &opts->page_object_lists->page[page], object);
}

static void
page_objects_list_set_page_object(fz_context *ctx, pdf_write_options *opts, int page, int object)
{
	page_objects_list_ensure(ctx, &opts->page_object_lists, page+1);
	opts->page_object_lists->page[page]->page_object_number = object;
}

static void
page_objects_sort(fz_context *ctx, page_objects *po)
{
	int i, j;
	int n = po->len;

	/* Step 1: Make a heap */
	/* Invariant: Valid heap in [0..i), unsorted elements in [i..n) */
	for (i = 1; i < n; i++)
	{
		/* Now bubble backwards to maintain heap invariant */
		j = i;
		while (j != 0)
		{
			int tmp;
			int k = (j-1)>>1;
			if (po->object[k] >= po->object[j])
				break;
			tmp = po->object[k];
			po->object[k] = po->object[j];
			po->object[j] = tmp;
			j = k;
		}
	}

	/* Step 2: Heap sort */
	/* Invariant: valid heap in [0..i), sorted list in [i..n) */
	/* Initially: i = n */
	for (i = n-1; i > 0; i--)
	{
		/* Swap the maximum (0th) element from the page_objects into its place
		 * in the sorted list (position i). */
		int tmp = po->object[0];
		po->object[0] = po->object[i];
		po->object[i] = tmp;
		/* Now, the page_objects is invalid because the 0th element is out
		 * of place. Bubble it until the page_objects is valid. */
		j = 0;
		while (1)
		{
			/* Children are k and k+1 */
			int k = (j+1)*2-1;
			/* If both children out of the page_objects, we're done */
			if (k > i-1)
				break;
			/* If both are in the page_objects, pick the larger one */
			if (k < i-1 && po->object[k] < po->object[k+1])
				k++;
			/* If j is bigger than k (i.e. both of it's children),
			 * we're done */
			if (po->object[j] > po->object[k])
				break;
			tmp = po->object[k];
			po->object[k] = po->object[j];
			po->object[j] = tmp;
			j = k;
		}
	}
}

static int
order_ge(int ui, int uj)
{
	/* For linearization, we need to order the sections as follows:
	 *  Remaining pages
	 *  Shared objects
	 *  Objects not associated with any page
	 *  (Linearization params)
	 *  Catalogue (and other document level objects)
	 *  First page
	 *  (Primary Hint stream) (*)
	 *  Any free objects
	 * Note, this is NOT the same order they appear in
	 * the final file!
	 *
	 * The PDF reference gives us the option of putting the hint stream
	 * after the first page, and we take it, for simplicity.
	 */
	/* If the 2 objects are in the same section, then page object comes
	 * first. */
	if (((ui ^ uj) & ~USE_PAGE_OBJECT) == 0)
		return ((ui & USE_PAGE_OBJECT) == 0);
	/* Put unused objects last */
	else if (ui == 0)
		return 1;
	else if (uj == 0)
		return 0;
	/* Put the hint stream before that... */
	else if (ui & USE_HINTS)
		return 1;
	else if (uj & USE_HINTS)
		return 0;
	/* Put page 1 before that... */
	else if (ui & USE_PAGE1)
		return 1;
	else if (uj & USE_PAGE1)
		return 0;
	/* Put the calagoue before that... */
	else if (ui & USE_CATALOGUE)
		return 1;
	else if (uj & USE_CATALOGUE)
		return 0;
	/* Put the linearization params before that... */
	else if (ui & USE_PARAMS)
		return 1;
	else if (uj & USE_PARAMS)
		return 0;
	/* Put objects not associated with any page (anything
	 * not touched by the catalogue) before that... */
	else if (ui == 0)
		return 1;
	else if (uj == 0)
		return 0;
	/* Put shared objects before that... */
	else if (ui & USE_SHARED)
		return 1;
	else if (uj & USE_SHARED)
		return 0;
	/* And otherwise, order by the page number on which
	 * they are used. */
	return (ui>>USE_PAGE_SHIFT) >= (uj>>USE_PAGE_SHIFT);
}

static void
heap_sort(int *list, int n, const int *val, int (*ge)(int, int))
{
	int i, j;

#ifdef DEBUG_HEAP_SORT
	fprintf(stderr, "Initially:\n");
	for (i=0; i < n; i++)
	{
		fprintf(stderr, "%d: %d %x\n", i, list[i], val[list[i]]);
	}
#endif
	/* Step 1: Make a heap */
	/* Invariant: Valid heap in [0..i), unsorted elements in [i..n) */
	for (i = 1; i < n; i++)
	{
		/* Now bubble backwards to maintain heap invariant */
		j = i;
		while (j != 0)
		{
			int tmp;
			int k = (j-1)>>1;
			if (ge(val[list[k]], val[list[j]]))
				break;
			tmp = list[k];
			list[k] = list[j];
			list[j] = tmp;
			j = k;
		}
	}
#ifdef DEBUG_HEAP_SORT
	fprintf(stderr, "Valid heap:\n");
	for (i=0; i < n; i++)
	{
		int k;
		fprintf(stderr, "%d: %d %x ", i, list[i], val[list[i]]);
		k = (i+1)*2-1;
		if (k < n)
		{
			if (ge(val[list[i]], val[list[k]]))
				fprintf(stderr, "OK ");
			else
				fprintf(stderr, "BAD ");
		}
		if (k+1 < n)
		{
			if (ge(val[list[i]], val[list[k+1]]))
				fprintf(stderr, "OK\n");
			else
				fprintf(stderr, "BAD\n");
		}
		else
				fprintf(stderr, "\n");
	}
#endif

	/* Step 2: Heap sort */
	/* Invariant: valid heap in [0..i), sorted list in [i..n) */
	/* Initially: i = n */
	for (i = n-1; i > 0; i--)
	{
		/* Swap the maximum (0th) element from the page_objects into its place
		 * in the sorted list (position i). */
		int tmp = list[0];
		list[0] = list[i];
		list[i] = tmp;
		/* Now, the page_objects is invalid because the 0th element is out
		 * of place. Bubble it until the page_objects is valid. */
		j = 0;
		while (1)
		{
			/* Children are k and k+1 */
			int k = (j+1)*2-1;
			/* If both children out of the page_objects, we're done */
			if (k > i-1)
				break;
			/* If both are in the page_objects, pick the larger one */
			if (k < i-1 && ge(val[list[k+1]], val[list[k]]))
				k++;
			/* If j is bigger than k (i.e. both of it's children),
			 * we're done */
			if (ge(val[list[j]], val[list[k]]))
				break;
			tmp = list[k];
			list[k] = list[j];
			list[j] = tmp;
			j = k;
		}
	}
#ifdef DEBUG_HEAP_SORT
	fprintf(stderr, "Sorted:\n");
	for (i=0; i < n; i++)
	{
		fprintf(stderr, "%d: %d %x ", i, list[i], val[list[i]]);
		if (i+1 < n)
		{
			if (ge(val[list[i+1]], val[list[i]]))
				fprintf(stderr, "OK");
			else
				fprintf(stderr, "BAD");
		}
		fprintf(stderr, "\n");
	}
#endif
}

static void
page_objects_dedupe(fz_context *ctx, page_objects *po)
{
	int i, j;
	int n = po->len-1;

	for (i = 0; i < n; i++)
	{
		if (po->object[i] == po->object[i+1])
			break;
	}
	j = i; /* j points to the last valid one */
	i++; /* i points to the first one we haven't looked at */
	for (; i < n; i++)
	{
		if (po->object[j] != po->object[i])
			po->object[++j] = po->object[i];
	}
	po->len = j+1;
}

static void
page_objects_list_sort_and_dedupe(fz_context *ctx, page_objects_list *pol)
{
	int i;
	int n = pol->len;

	for (i = 0; i < n; i++)
	{
		page_objects_sort(ctx, pol->page[i]);
		page_objects_dedupe(ctx, pol->page[i]);
	}
}

#ifdef DEBUG_LINEARIZATION
static void
page_objects_dump(pdf_write_options *opts)
{
	page_objects_list *pol = opts->page_object_lists;
	int i, j;

	for (i = 0; i < pol->len; i++)
	{
		page_objects *p = pol->page[i];
		fprintf(stderr, "Page %d\n", i+1);
		for (j = 0; j < p->len; j++)
		{
			int o = p->object[j];
			fprintf(stderr, "  Object %d: use=%x\n", o, opts->use_list[o]);
		}
		fprintf(stderr, "Byte range=%d->%d\n", p->min_ofs, p->max_ofs);
		fprintf(stderr, "Number of objects=%d, Number of shared objects=%d\n", p->num_objects, p->num_shared);
		fprintf(stderr, "Page object number=%d\n", p->page_object_number);
	}
}

static void
objects_dump(pdf_document *xref, pdf_write_options *opts)
{
	int i;

	for (i=0; i < xref->len; i++)
	{
		fprintf(stderr, "Object %d use=%x offset=%d\n", i, opts->use_list[i], opts->ofs_list[i]);
	}
}
#endif

/*
 * Garbage collect objects not reachable from the trailer.
 */

static pdf_obj *sweepref(pdf_document *xref, pdf_write_options *opts, pdf_obj *obj)
{
	int num = pdf_to_num(obj);
	int gen = pdf_to_gen(obj);
	fz_context *ctx = xref->ctx;

	if (num < 0 || num >= xref->len)
		return NULL;
	if (opts->use_list[num])
		return NULL;

	opts->use_list[num] = 1;

	/* Bake in /Length in stream objects */
	fz_try(ctx)
	{
		if (pdf_is_stream(xref, num, gen))
		{
			pdf_obj *len = pdf_dict_gets(obj, "Length");
			if (pdf_is_indirect(len))
			{
				opts->use_list[pdf_to_num(len)] = 0;
				len = pdf_resolve_indirect(len);
				pdf_dict_puts(obj, "Length", len);
			}
		}
	}
	fz_catch(ctx)
	{
		/* Leave broken */
	}

	return pdf_resolve_indirect(obj);
}

static void sweepobj(pdf_document *xref, pdf_write_options *opts, pdf_obj *obj)
{
	int i;

	if (pdf_is_indirect(obj))
		obj = sweepref(xref, opts, obj);

	if (pdf_is_dict(obj))
	{
		int n = pdf_dict_len(obj);
		for (i = 0; i < n; i++)
			sweepobj(xref, opts, pdf_dict_get_val(obj, i));
	}

	else if (pdf_is_array(obj))
	{
		int n = pdf_array_len(obj);
		for (i = 0; i < n; i++)
			sweepobj(xref, opts, pdf_array_get(obj, i));
	}
}

/*
 * Scan for and remove duplicate objects (slow)
 */

static void removeduplicateobjs(pdf_document *xref, pdf_write_options *opts)
{
	int num, other;
	fz_context *ctx = xref->ctx;

	for (num = 1; num < xref->len; num++)
	{
		/* Only compare an object to objects preceding it */
		for (other = 1; other < num; other++)
		{
			pdf_obj *a, *b;
			int differ, newnum;

			if (num == other || !opts->use_list[num] || !opts->use_list[other])
				continue;

			/*
			 * Comparing stream objects data contents would take too long.
			 *
			 * pdf_is_stream calls pdf_cache_object and ensures
			 * that the xref table has the objects loaded.
			 */
			fz_try(ctx)
			{
				differ = (pdf_is_stream(xref, num, 0) || pdf_is_stream(xref, other, 0));
			}
			fz_catch(ctx)
			{
				/* Assume different */
				differ = 1;
			}
			if (differ)
				continue;

			a = xref->table[num].obj;
			b = xref->table[other].obj;

			a = pdf_resolve_indirect(a);
			b = pdf_resolve_indirect(b);

			if (pdf_objcmp(a, b))
				continue;

			/* Keep the lowest numbered object */
			newnum = fz_mini(num, other);
			opts->renumber_map[num] = newnum;
			opts->renumber_map[other] = newnum;
			opts->rev_renumber_map[newnum] = num; /* Either will do */
			opts->use_list[fz_maxi(num, other)] = 0;

			/* One duplicate was found, do not look for another */
			break;
		}
	}
}

/*
 * Renumber objects sequentially so the xref is more compact
 *
 * This code assumes that any opts->renumber_map[n] <= n for all n.
 */

static void compactxref(pdf_document *xref, pdf_write_options *opts)
{
	int num, newnum;

	/*
	 * Update renumber_map in-place, clustering all used
	 * objects together at low object ids. Objects that
	 * already should be renumbered will have their new
	 * object ids be updated to reflect the compaction.
	 */

	newnum = 1;
	for (num = 1; num < xref->len; num++)
	{
		/* If it's not used, map it to zero */
		if (!opts->use_list[opts->renumber_map[num]])
		{
			opts->renumber_map[num] = 0;
		}
		/* If it's not moved, compact it. */
		else if (opts->renumber_map[num] == num)
		{
			opts->rev_renumber_map[newnum] = opts->rev_renumber_map[num];
			opts->rev_gen_list[newnum] = opts->rev_gen_list[num];
			opts->renumber_map[num] = newnum++;
		}
		/* Otherwise it's used, and moved. We know that it must have
		 * moved down, so the place it's moved to will be in the right
		 * place already. */
		else
		{
			opts->renumber_map[num] = opts->renumber_map[opts->renumber_map[num]];
		}
	}
}

/*
 * Update indirect objects according to renumbering established when
 * removing duplicate objects and compacting the xref.
 */

static void renumberobj(pdf_document *xref, pdf_write_options *opts, pdf_obj *obj)
{
	int i;
	fz_context *ctx = xref->ctx;

	if (pdf_is_dict(obj))
	{
		int n = pdf_dict_len(obj);
		for (i = 0; i < n; i++)
		{
			pdf_obj *key = pdf_dict_get_key(obj, i);
			pdf_obj *val = pdf_dict_get_val(obj, i);
			if (pdf_is_indirect(val))
			{
				val = pdf_new_indirect(ctx, opts->renumber_map[pdf_to_num(val)], 0, xref);
				pdf_dict_put(obj, key, val);
				pdf_drop_obj(val);
			}
			else
			{
				renumberobj(xref, opts, val);
			}
		}
	}

	else if (pdf_is_array(obj))
	{
		int n = pdf_array_len(obj);
		for (i = 0; i < n; i++)
		{
			pdf_obj *val = pdf_array_get(obj, i);
			if (pdf_is_indirect(val))
			{
				val = pdf_new_indirect(ctx, opts->renumber_map[pdf_to_num(val)], 0, xref);
				pdf_array_put(obj, i, val);
				pdf_drop_obj(val);
			}
			else
			{
				renumberobj(xref, opts, val);
			}
		}
	}
}

static void renumberobjs(pdf_document *xref, pdf_write_options *opts)
{
	pdf_xref_entry *oldxref;
	int newlen;
	int num;
	fz_context *ctx = xref->ctx;
	int *new_use_list;

	new_use_list = fz_calloc(ctx, xref->len+3, sizeof(int));

	fz_try(ctx)
	{
		/* Apply renumber map to indirect references in all objects in xref */
		renumberobj(xref, opts, xref->trailer);
		for (num = 0; num < xref->len; num++)
		{
			pdf_obj *obj = xref->table[num].obj;

			if (pdf_is_indirect(obj))
			{
				obj = pdf_new_indirect(ctx, opts->renumber_map[pdf_to_num(obj)], 0, xref);
				pdf_update_object(xref, num, obj);
				pdf_drop_obj(obj);
			}
			else
			{
				renumberobj(xref, opts, obj);
			}
		}

		/* Create new table for the reordered, compacted xref */
		oldxref = xref->table;
		xref->table = fz_malloc_array(ctx, xref->len + 3, sizeof(pdf_xref_entry));
		xref->table[0] = oldxref[0];

		/* Move used objects into the new compacted xref */
		newlen = 0;
		for (num = 1; num < xref->len; num++)
		{
			if (opts->use_list[num])
			{
				if (newlen < opts->renumber_map[num])
					newlen = opts->renumber_map[num];
				xref->table[opts->renumber_map[num]] = oldxref[num];
				new_use_list[opts->renumber_map[num]] = opts->use_list[num];
			}
			else
			{
				pdf_drop_obj(oldxref[num].obj);
			}
		}
	}
	fz_catch(ctx)
	{
		fz_free(ctx, new_use_list);
		fz_rethrow(ctx);
	}
	fz_free(ctx, oldxref);
	fz_free(ctx, opts->use_list);
	opts->use_list = new_use_list;

	/* Update the used objects count in compacted xref */
	xref->len = newlen + 1;

	for (num = 1; num < xref->len; num++)
	{
		opts->renumber_map[num] = num;
	}
}

static void page_objects_list_renumber(pdf_write_options *opts)
{
	int i, j;

	for (i = 0; i < opts->page_object_lists->len; i++)
	{
		page_objects *po = opts->page_object_lists->page[i];
		for (j = 0; j < po->len; j++)
		{
			po->object[j] = opts->renumber_map[po->object[j]];
		}
		po->page_object_number = opts->renumber_map[po->page_object_number];
	}
}

static void
mark_all(pdf_document *xref, pdf_write_options *opts, pdf_obj *val, int flag, int page)
{
	fz_context *ctx = xref->ctx;

	if (pdf_dict_mark(val))
		return;

	fz_try(ctx)
	{
		if (pdf_is_indirect(val))
		{
			int num = pdf_to_num(val);
			if (flag >= 16 && (opts->use_list[num] & USE_PAGE_MASK))
				/* Already used */
				opts->use_list[num] |= USE_SHARED;
			else
				opts->use_list[num] |= flag;
			if (page >= 0)
				page_objects_list_insert(ctx, opts, page, num);
		}

		if (pdf_is_dict(val))
		{
			int i, n = pdf_dict_len(val);

			for (i = 0; i < n; i++)
			{
				mark_all(xref, opts, pdf_dict_get_val(val, i), flag, page);
			}
		}
		else if (pdf_is_array(val))
		{
			int i, n = pdf_array_len(val);

			for (i = 0; i < n; i++)
			{
				mark_all(xref, opts, pdf_array_get(val, i), flag, page);
			}
		}
	}
	fz_always(ctx)
	{
		pdf_dict_unmark(val);
	}
	fz_catch(ctx)
	{
		fz_rethrow(ctx);
	}
}

static int
mark_pages(pdf_document *xref, pdf_write_options *opts, pdf_obj *val, int pagenum)
{
	fz_context *ctx = xref->ctx;

	if (pdf_dict_mark(val))
		return pagenum;

	fz_try(ctx)
	{
		if (pdf_is_dict(val))
		{
			if (!strcmp("Page", pdf_to_name(pdf_dict_gets(val, "Type"))))
			{
				int num = pdf_to_num(val);
				pdf_dict_unmark(val);
				mark_all(xref, opts, val, pagenum == 0 ? USE_PAGE1 : (pagenum<<USE_PAGE_SHIFT), pagenum);
				page_objects_list_set_page_object(ctx, opts, pagenum, num);
				pagenum++;
				opts->use_list[num] |= USE_PAGE_OBJECT;
			}
			else
			{
				int i, n = pdf_dict_len(val);

				for (i = 0; i < n; i++)
				{
					pdf_obj *key = pdf_dict_get_key(val, i);
					pdf_obj *obj = pdf_dict_get_val(val, i);

					if (!strcmp("Kids", pdf_to_name(key)))
						pagenum = mark_pages(xref, opts, obj, pagenum);
					else
						mark_all(xref, opts, obj, USE_CATALOGUE, -1);
				}

				if (pdf_is_indirect(val))
				{
					int num = pdf_to_num(val);
					opts->use_list[num] |= USE_CATALOGUE;
				}
			}
		}
		else if (pdf_is_array(val))
		{
			int i, n = pdf_array_len(val);

			for (i = 0; i < n; i++)
			{
				pagenum = mark_pages(xref, opts, pdf_array_get(val, i), pagenum);
			}
			if (pdf_is_indirect(val))
			{
				int num = pdf_to_num(val);
				opts->use_list[num] |= USE_CATALOGUE;
			}
		}
	}
	fz_always(ctx)
	{
		pdf_dict_unmark(val);
	}
	fz_catch(ctx)
	{
		fz_rethrow(ctx);
	}
	return pagenum;
}

static void
mark_root(pdf_document *xref, pdf_write_options *opts, pdf_obj *dict)
{
	fz_context *ctx = xref->ctx;
	int i, n = pdf_dict_len(dict);

	if (pdf_dict_mark(dict))
		return;

	fz_try(ctx)
	{
		if (pdf_is_indirect(dict))
		{
			int num = pdf_to_num(dict);
			opts->use_list[num] |= USE_CATALOGUE;
		}

		for (i = 0; i < n; i++)
		{
			char *key = pdf_to_name(pdf_dict_get_key(dict, i));
			pdf_obj *val = pdf_dict_get_val(dict, i);

			if (!strcmp("Pages", key))
				opts->page_count = mark_pages(xref, opts, val, 0);
			else if (!strcmp("Outlines", key))
			{
				/* FIXME: Look at PageMode to decide whether to
				 * USE_OTHERPAGES or USE_PAGE1 here. */
				if (0 /* PageMode == "Outlines" */)
					mark_all(xref, opts, val, USE_PAGE1, -1);
			}
			else
				mark_all(xref, opts, val, USE_CATALOGUE, -1);
		}
	}
	fz_always(ctx)
	{
		pdf_dict_unmark(dict);
	}
	fz_catch(ctx)
	{
		fz_rethrow(ctx);
	}
}

static void
mark_trailer(pdf_document *xref, pdf_write_options *opts, pdf_obj *dict)
{
	fz_context *ctx = xref->ctx;
	int i, n = pdf_dict_len(dict);

	if (pdf_dict_mark(dict))
		return;

	fz_try(ctx)
	{
		for (i = 0; i < n; i++)
		{
			char *key = pdf_to_name(pdf_dict_get_key(dict, i));
			pdf_obj *val = pdf_dict_get_val(dict, i);

			if (!strcmp("Root", key))
				mark_root(xref, opts, val);
			else
				mark_all(xref, opts, val, USE_CATALOGUE, -1);
		}
	}
	fz_always(ctx)
	{
		pdf_dict_unmark(dict);
	}
	fz_catch(ctx)
	{
		fz_rethrow(ctx);
	}
}

static void
add_linearization_objs(pdf_document *xref, pdf_write_options *opts)
{
	pdf_obj *params_obj = NULL;
	pdf_obj *params_ref = NULL;
	pdf_obj *hint_obj = NULL;
	pdf_obj *hint_ref = NULL;
	pdf_obj *o = NULL;
	int params_num, hint_num;
	fz_context *ctx = xref->ctx;

	fz_var(params_obj);
	fz_var(params_ref);
	fz_var(hint_obj);
	fz_var(hint_ref);
	fz_var(o);

	fz_try(ctx)
	{
		/* Linearization params */
		params_obj = pdf_new_dict(ctx, 10);
		params_ref = pdf_new_ref(xref, params_obj);
		params_num = pdf_to_num(params_ref);

		opts->use_list[params_num] = USE_PARAMS;
		opts->renumber_map[params_num] = params_num;
		opts->rev_renumber_map[params_num] = params_num;
		opts->gen_list[params_num] = 0;
		opts->rev_gen_list[params_num] = 0;
		pdf_dict_puts_drop(params_obj, "Linearized", pdf_new_real(ctx, 1.0));
		opts->linear_l = pdf_new_int(ctx, INT_MIN);
		pdf_dict_puts(params_obj, "L", opts->linear_l);
		opts->linear_h0 = pdf_new_int(ctx, INT_MIN);
		o = pdf_new_array(ctx, 2);
		pdf_array_push(o, opts->linear_h0);
		opts->linear_h1 = pdf_new_int(ctx, INT_MIN);
		pdf_array_push(o, opts->linear_h1);
		pdf_dict_puts_drop(params_obj, "H", o);
		o = NULL;
		opts->linear_o = pdf_new_int(ctx, INT_MIN);
		pdf_dict_puts(params_obj, "O", opts->linear_o);
		opts->linear_e = pdf_new_int(ctx, INT_MIN);
		pdf_dict_puts(params_obj, "E", opts->linear_e);
		opts->linear_n = pdf_new_int(ctx, INT_MIN);
		pdf_dict_puts(params_obj, "N", opts->linear_n);
		opts->linear_t = pdf_new_int(ctx, INT_MIN);
		pdf_dict_puts(params_obj, "T", opts->linear_t);

		/* Primary hint stream */
		hint_obj = pdf_new_dict(ctx, 10);
		hint_ref = pdf_new_ref(xref, hint_obj);
		hint_num = pdf_to_num(hint_ref);

		opts->use_list[hint_num] = USE_HINTS;
		opts->renumber_map[hint_num] = hint_num;
		opts->rev_renumber_map[hint_num] = hint_num;
		opts->gen_list[hint_num] = 0;
		opts->rev_gen_list[hint_num] = 0;
		pdf_dict_puts_drop(hint_obj, "P", pdf_new_int(ctx, 0));
		opts->hints_s = pdf_new_int(ctx, INT_MIN);
		pdf_dict_puts(hint_obj, "S", opts->hints_s);
		/* FIXME: Do we have thumbnails? Do a T entry */
		/* FIXME: Do we have outlines? Do an O entry */
		/* FIXME: Do we have article threads? Do an A entry */
		/* FIXME: Do we have named destinations? Do a E entry */
		/* FIXME: Do we have interactive forms? Do a V entry */
		/* FIXME: Do we have document information? Do an I entry */
		/* FIXME: Do we have logical structure heirarchy? Do a C entry */
		/* FIXME: Do L, Page Label hint table */
		pdf_dict_puts_drop(hint_obj, "Filter", pdf_new_name(ctx, "FlateDecode"));
		opts->hints_length = pdf_new_int(ctx, INT_MIN);
		pdf_dict_puts(hint_obj, "Length", opts->hints_length);
		xref->table[hint_num].stm_ofs = -1;
	}
	fz_always(ctx)
	{
		pdf_drop_obj(params_obj);
		pdf_drop_obj(params_ref);
		pdf_drop_obj(hint_ref);
		pdf_drop_obj(hint_obj);
		pdf_drop_obj(o);
	}
	fz_catch(ctx)
	{
		fz_rethrow(ctx);
	}
}

static void
lpr_inherit_res_contents(fz_context *ctx, pdf_obj *res, pdf_obj *dict, char *text)
{
	pdf_obj *o, *r;
	int i, n;

	/* If the parent node doesn't have an entry of this type, give up. */
	o = pdf_dict_gets(dict, text);
	if (!o)
		return;

	/* If the resources dict we are building doesn't have an entry of this
	 * type yet, then just copy it (ensuring it's not a reference) */
	r = pdf_dict_gets(res, text);
	if (r == NULL)
	{
		o = pdf_resolve_indirect(o);
		if (pdf_is_dict(o))
			o = pdf_copy_dict(ctx, o);
		else if (pdf_is_array(o))
			o = pdf_copy_array(ctx, o);
		else
			o = NULL;
		if (o)
			pdf_dict_puts(res, text, o);
		return;
	}

	/* Otherwise we need to merge o into r */
	if (pdf_is_dict(o))
	{
		n = pdf_dict_len(o);
		for (i = 0; i < n; i++)
		{
			pdf_obj *key = pdf_dict_get_key(o, i);
			pdf_obj *val = pdf_dict_get_val(o, i);

			if (pdf_dict_gets(res, pdf_to_name(key)))
				continue;
			pdf_dict_puts(res, pdf_to_name(key), val);
		}
	}
}

static void
lpr_inherit_res(fz_context *ctx, pdf_obj *node, int depth, pdf_obj *dict)
{
	while (1)
	{
		pdf_obj *o;

		node = pdf_dict_gets(node, "Parent");
		depth--;
		if (!node || depth < 0)
			break;

		o = pdf_dict_gets(node, "Resources");
		if (o)
		{
			lpr_inherit_res_contents(ctx, dict, o, "ExtGState");
			lpr_inherit_res_contents(ctx, dict, o, "ColorSpace");
			lpr_inherit_res_contents(ctx, dict, o, "Pattern");
			lpr_inherit_res_contents(ctx, dict, o, "Shading");
			lpr_inherit_res_contents(ctx, dict, o, "XObject");
			lpr_inherit_res_contents(ctx, dict, o, "Font");
			lpr_inherit_res_contents(ctx, dict, o, "ProcSet");
			lpr_inherit_res_contents(ctx, dict, o, "Properties");
		}
	}
}

static pdf_obj *
lpr_inherit(fz_context *ctx, pdf_obj *node, char *text, int depth)
{
	do
	{
		pdf_obj *o = pdf_dict_gets(node, text);

		if (o)
			return pdf_resolve_indirect(o);
		node = pdf_dict_gets(node, "Parent");
		depth--;
	}
	while (depth >= 0 && node);

	return NULL;
}

static int
lpr(fz_context *ctx, pdf_obj *node, int depth, int page)
{
	pdf_obj *kids;
	pdf_obj *o = NULL;
	int i, n;

	if (pdf_dict_mark(node))
		return page;

	fz_var(o);

	fz_try(ctx)
	{
		if (!strcmp("Page", pdf_to_name(pdf_dict_gets(node, "Type"))))
		{
			pdf_obj *r; /* r is deliberately not cleaned up */

			/* Copy resources down to the child */
			o = pdf_keep_obj(pdf_dict_gets(node, "Resources"));
			if (!o)
			{
				o = pdf_keep_obj(pdf_new_dict(ctx, 2));
				pdf_dict_puts(node, "Resources", o);
			}
			lpr_inherit_res(ctx, node, depth, o);
			r = lpr_inherit(ctx, node, "MediaBox", depth);
			if (r)
				pdf_dict_puts(node, "MediaBox", r);
			r = lpr_inherit(ctx, node, "CropBox", depth);
			if (r)
				pdf_dict_puts(node, "CropBox", r);
			r = lpr_inherit(ctx, node, "BleedBox", depth);
			if (r)
				pdf_dict_puts(node, "BleedBox", r);
			r = lpr_inherit(ctx, node, "TrimBox", depth);
			if (r)
				pdf_dict_puts(node, "TrimBox", r);
			r = lpr_inherit(ctx, node, "ArtBox", depth);
			if (r)
				pdf_dict_puts(node, "ArtBox", r);
			r = lpr_inherit(ctx, node, "Rotate", depth);
			if (r)
				pdf_dict_puts(node, "Rotate", r);
			page++;
		}
		else
		{
			kids = pdf_dict_gets(node, "Kids");
			n = pdf_array_len(kids);
			for(i = 0; i < n; i++)
			{
				page = lpr(ctx, pdf_array_get(kids, i), depth+1, page);
			}
			pdf_dict_dels(node, "Resources");
			pdf_dict_dels(node, "MediaBox");
			pdf_dict_dels(node, "CropBox");
			pdf_dict_dels(node, "BleedBox");
			pdf_dict_dels(node, "TrimBox");
			pdf_dict_dels(node, "ArtBox");
			pdf_dict_dels(node, "Rotate");
		}
	}
	fz_always(ctx)
	{
		pdf_drop_obj(o);
	}
	fz_catch(ctx)
	{
		fz_rethrow(ctx);
	}

	pdf_dict_unmark(node);

	return page;
}

void
pdf_localise_page_resources(pdf_document *xref)
{
	fz_context *ctx = xref->ctx;

	if (xref->resources_localised)
		return;

	lpr(ctx, pdf_dict_getp(xref->trailer, "Root/Pages"), 0, 0);

	xref->resources_localised = 1;
}

static void
linearize(pdf_document *xref, pdf_write_options *opts)
{
	int i;
	int n = xref->len + 2;
	int *reorder;
	int *rev_renumber_map;
	int *rev_gen_list;
	fz_context *ctx = xref->ctx;

	opts->page_object_lists = page_objects_list_create(ctx);

	/* Ensure that every page has local references of its resources */
	/* FIXME: We could 'thin' the resources according to what is actually
	 * required for each page, but this would require us to run the page
	 * content streams. */
	pdf_localise_page_resources(xref);

	/* Walk the objects for each page, marking which ones are used, where */
	memset(opts->use_list, 0, n * sizeof(int));
	mark_trailer(xref, opts, xref->trailer);

	/* Add new objects required for linearization */
	add_linearization_objs(xref, opts);

#ifdef DEBUG_WRITING
	fprintf(stderr, "Usage calculated:\n");
	for (i=0; i < xref->len; i++)
	{
		fprintf(stderr, "%d: use=%d\n", i, opts->use_list[i]);
	}
#endif

	/* Allocate/init the structures used for renumbering the objects */
	reorder = fz_calloc(ctx, n, sizeof(int));
	rev_renumber_map = fz_calloc(ctx, n, sizeof(int));
	rev_gen_list = fz_calloc(ctx, n, sizeof(int));
	for (i = 0; i < n; i++)
	{
		reorder[i] = i;
	}

	/* Heap sort the reordering */
	heap_sort(reorder+1, n-1, opts->use_list, &order_ge);

#ifdef DEBUG_WRITING
	fprintf(stderr, "Reordered:\n");
	for (i=1; i < xref->len; i++)
	{
		fprintf(stderr, "%d: use=%d\n", i, opts->use_list[reorder[i]]);
	}
#endif

	/* Find the split point */
	for (i = 1; (opts->use_list[reorder[i]] & USE_PARAMS) == 0; i++);
	opts->start = i;

	/* Roll the reordering into the renumber_map */
	for (i = 0; i < n; i++)
	{
		opts->renumber_map[reorder[i]] = i;
		rev_renumber_map[i] = opts->rev_renumber_map[reorder[i]];
		rev_gen_list[i] = opts->rev_gen_list[reorder[i]];
	}
	fz_free(ctx, opts->rev_renumber_map);
	fz_free(ctx, opts->rev_gen_list);
	opts->rev_renumber_map = rev_renumber_map;
	opts->rev_gen_list = rev_gen_list;
	fz_free(ctx, reorder);

	/* Apply the renumber_map */
	page_objects_list_renumber(opts);
	renumberobjs(xref, opts);

	page_objects_list_sort_and_dedupe(ctx, opts->page_object_lists);
}

static void
update_linearization_params(pdf_document *xref, pdf_write_options *opts)
{
	int offset;
	pdf_set_int(opts->linear_l, opts->file_len);
	/* Primary hint stream offset (of object, not stream!) */
	pdf_set_int(opts->linear_h0, opts->ofs_list[xref->len-1]);
	/* Primary hint stream length (of object, not stream!) */
	offset = (opts->start == 1 ? opts->main_xref_offset : opts->ofs_list[1] + opts->hintstream_len);
	pdf_set_int(opts->linear_h1, offset - opts->ofs_list[xref->len-1]);
	/* Object number of first pages page object (the first object of page 0) */
	pdf_set_int(opts->linear_o, opts->page_object_lists->page[0]->object[0]);
	/* Offset of end of first page (first page is followed by primary
	 * hint stream (object n-1) then remaining pages (object 1...). The
	 * primary hint stream counts as part of the first pages data, I think.
	 */
	offset = (opts->start == 1 ? opts->main_xref_offset : opts->ofs_list[1] + opts->hintstream_len);
	pdf_set_int(opts->linear_e, offset);
	/* Number of pages in document */
	pdf_set_int(opts->linear_n, opts->page_count);
	/* Offset of first entry in main xref table */
	pdf_set_int(opts->linear_t, opts->first_xref_entry_offset + opts->hintstream_len);
	/* Offset of shared objects hint table in the primary hint stream */
	pdf_set_int(opts->hints_s, opts->hints_shared_offset);
	/* Primary hint stream length */
	pdf_set_int(opts->hints_length, opts->hintstream_len);
}


/*
 * Make sure we have loaded objects from object streams.
 */

static void preloadobjstms(pdf_document *xref)
{
	pdf_obj *obj;
	int num;

	for (num = 0; num < xref->len; num++)
	{
		if (xref->table[num].type == 'o')
		{
			obj = pdf_load_object(xref, num, 0);
			pdf_drop_obj(obj);
		}
	}
}

/*
 * Save streams and objects to the output
 */

static inline int isbinary(int c)
{
	if (c == '\n' || c == '\r' || c == '\t')
		return 0;
	return c < 32 || c > 127;
}

static int isbinarystream(fz_buffer *buf)
{
	int i;
	for (i = 0; i < buf->len; i++)
		if (isbinary(buf->data[i]))
			return 1;
	return 0;
}

static fz_buffer *hexbuf(fz_context *ctx, unsigned char *p, int n)
{
	static const char hex[16] = "0123456789abcdef";
	fz_buffer *buf;
	int x = 0;

	buf = fz_new_buffer(ctx, n * 2 + (n / 32) + 2);

	while (n--)
	{
		buf->data[buf->len++] = hex[*p >> 4];
		buf->data[buf->len++] = hex[*p & 15];
		if (++x == 32)
		{
			buf->data[buf->len++] = '\n';
			x = 0;
		}
		p++;
	}

	buf->data[buf->len++] = '>';
	buf->data[buf->len++] = '\n';

	return buf;
}

static void addhexfilter(pdf_document *xref, pdf_obj *dict)
{
	pdf_obj *f, *dp, *newf, *newdp;
	pdf_obj *ahx, *nullobj;
	fz_context *ctx = xref->ctx;

	ahx = pdf_new_name(ctx, "ASCIIHexDecode");
	nullobj = pdf_new_null(ctx);
	newf = newdp = NULL;

	f = pdf_dict_gets(dict, "Filter");
	dp = pdf_dict_gets(dict, "DecodeParms");

	if (pdf_is_name(f))
	{
		newf = pdf_new_array(ctx, 2);
		pdf_array_push(newf, ahx);
		pdf_array_push(newf, f);
		f = newf;
		if (pdf_is_dict(dp))
		{
			newdp = pdf_new_array(ctx, 2);
			pdf_array_push(newdp, nullobj);
			pdf_array_push(newdp, dp);
			dp = newdp;
		}
	}
	else if (pdf_is_array(f))
	{
		pdf_array_insert(f, ahx);
		if (pdf_is_array(dp))
			pdf_array_insert(dp, nullobj);
	}
	else
		f = ahx;

	pdf_dict_puts(dict, "Filter", f);
	if (dp)
		pdf_dict_puts(dict, "DecodeParms", dp);

	pdf_drop_obj(ahx);
	pdf_drop_obj(nullobj);
	pdf_drop_obj(newf);
	pdf_drop_obj(newdp);
}

static void copystream(pdf_document *xref, pdf_write_options *opts, pdf_obj *obj_orig, int num, int gen)
{
	fz_buffer *buf, *tmp;
	pdf_obj *newlen;
	pdf_obj *obj;
	fz_context *ctx = xref->ctx;
	int orig_num = opts->rev_renumber_map[num];
	int orig_gen = opts->rev_gen_list[num];

	buf = pdf_load_raw_renumbered_stream(xref, num, gen, orig_num, orig_gen);

	obj = pdf_copy_dict(ctx, obj_orig);
	if (opts->do_ascii && isbinarystream(buf))
	{
		tmp = hexbuf(ctx, buf->data, buf->len);
		fz_drop_buffer(ctx, buf);
		buf = tmp;

		addhexfilter(xref, obj);

		newlen = pdf_new_int(ctx, buf->len);
		pdf_dict_puts(obj, "Length", newlen);
		pdf_drop_obj(newlen);
	}

	fprintf(opts->out, "%d %d obj\n", num, gen);
	pdf_fprint_obj(opts->out, obj, opts->do_expand == 0);
	fprintf(opts->out, "stream\n");
	fwrite(buf->data, 1, buf->len, opts->out);
	fprintf(opts->out, "endstream\nendobj\n\n");

	fz_drop_buffer(ctx, buf);
	pdf_drop_obj(obj);
}

static void expandstream(pdf_document *xref, pdf_write_options *opts, pdf_obj *obj_orig, int num, int gen)
{
	fz_buffer *buf, *tmp;
	pdf_obj *newlen;
	pdf_obj *obj;
	fz_context *ctx = xref->ctx;
	int orig_num = opts->rev_renumber_map[num];
	int orig_gen = opts->rev_gen_list[num];

	buf = pdf_load_renumbered_stream(xref, num, gen, orig_num, orig_gen);

	obj = pdf_copy_dict(ctx, obj_orig);
	pdf_dict_dels(obj, "Filter");
	pdf_dict_dels(obj, "DecodeParms");

	if (opts->do_ascii && isbinarystream(buf))
	{
		tmp = hexbuf(ctx, buf->data, buf->len);
		fz_drop_buffer(ctx, buf);
		buf = tmp;

		addhexfilter(xref, obj);
	}

	newlen = pdf_new_int(ctx, buf->len);
	pdf_dict_puts(obj, "Length", newlen);
	pdf_drop_obj(newlen);

	fprintf(opts->out, "%d %d obj\n", num, gen);
	pdf_fprint_obj(opts->out, obj, opts->do_expand == 0);
	fprintf(opts->out, "stream\n");
	fwrite(buf->data, 1, buf->len, opts->out);
	fprintf(opts->out, "endstream\nendobj\n\n");

	fz_drop_buffer(ctx, buf);
	pdf_drop_obj(obj);
}

static int is_image_filter(char *s)
{
	if (	!strcmp(s, "CCITTFaxDecode") || !strcmp(s, "CCF") ||
		!strcmp(s, "DCTDecode") || !strcmp(s, "DCT") ||
		!strcmp(s, "RunLengthDecode") || !strcmp(s, "RL") ||
		!strcmp(s, "JBIG2Decode") ||
		!strcmp(s, "JPXDecode"))
		return 1;
	return 0;
}

static int filter_implies_image(pdf_document *xref, pdf_obj *o)
{
	if (!o)
		return 0;
	if (pdf_is_name(o))
		return is_image_filter(pdf_to_name(o));
	if (pdf_is_array(o))
	{
		int i, len;
		len = pdf_array_len(o);
		for (i = 0; i < len; i++)
			if (is_image_filter(pdf_to_name(pdf_array_get(o, i))))
				return 1;
	}
	return 0;
}

static void writeobject(pdf_document *xref, pdf_write_options *opts, int num, int gen)
{
	pdf_obj *obj;
	pdf_obj *type;
	fz_context *ctx = xref->ctx;

	obj = pdf_load_object(xref, num, gen);

	/* skip ObjStm and XRef objects */
	if (pdf_is_dict(obj))
	{
		type = pdf_dict_gets(obj, "Type");
		if (pdf_is_name(type) && !strcmp(pdf_to_name(type), "ObjStm"))
		{
			opts->use_list[num] = 0;
			pdf_drop_obj(obj);
			return;
		}
		if (pdf_is_name(type) && !strcmp(pdf_to_name(type), "XRef"))
		{
			opts->use_list[num] = 0;
			pdf_drop_obj(obj);
			return;
		}
	}

	if (!pdf_is_stream(xref, num, gen))
	{
		fprintf(opts->out, "%d %d obj\n", num, gen);
		pdf_fprint_obj(opts->out, obj, opts->do_expand == 0);
		fprintf(opts->out, "endobj\n\n");
	}
	else if (xref->table[num].stm_ofs < 0 && xref->table[num].stm_buf == NULL)
	{
		fprintf(opts->out, "%d %d obj\n", num, gen);
		pdf_fprint_obj(opts->out, obj, opts->do_expand == 0);
		fprintf(opts->out, "stream\nendstream\nendobj\n\n");
	}
	else
	{
		int dontexpand = 0;
		if (opts->do_expand != 0 && opts->do_expand != fz_expand_all)
		{
			pdf_obj *o;

			if ((o = pdf_dict_gets(obj, "Type"), !strcmp(pdf_to_name(o), "XObject")) &&
				(o = pdf_dict_gets(obj, "Subtype"), !strcmp(pdf_to_name(o), "Image")))
				dontexpand = !(opts->do_expand & fz_expand_images);
			if (o = pdf_dict_gets(obj, "Type"), !strcmp(pdf_to_name(o), "Font"))
				dontexpand = !(opts->do_expand & fz_expand_fonts);
			if (o = pdf_dict_gets(obj, "Type"), !strcmp(pdf_to_name(o), "FontDescriptor"))
				dontexpand = !(opts->do_expand & fz_expand_fonts);
			if ((o = pdf_dict_gets(obj, "Length1")) != NULL)
				dontexpand = !(opts->do_expand & fz_expand_fonts);
			if ((o = pdf_dict_gets(obj, "Length2")) != NULL)
				dontexpand = !(opts->do_expand & fz_expand_fonts);
			if ((o = pdf_dict_gets(obj, "Length3")) != NULL)
				dontexpand = !(opts->do_expand & fz_expand_fonts);
			if (o = pdf_dict_gets(obj, "Subtype"), !strcmp(pdf_to_name(o), "Type1C"))
				dontexpand = !(opts->do_expand & fz_expand_fonts);
			if (o = pdf_dict_gets(obj, "Subtype"), !strcmp(pdf_to_name(o), "CIDFontType0C"))
				dontexpand = !(opts->do_expand & fz_expand_fonts);
			if (o = pdf_dict_gets(obj, "Filter"), filter_implies_image(xref, o))
				dontexpand = !(opts->do_expand & fz_expand_images);
			if (pdf_dict_gets(obj, "Width") != NULL && pdf_dict_gets(obj, "Height") != NULL)
				dontexpand = !(opts->do_expand & fz_expand_images);
		}
		if (opts->do_expand && !dontexpand && !pdf_is_jpx_image(ctx, obj))
			expandstream(xref, opts, obj, num, gen);
		else
			copystream(xref, opts, obj, num, gen);
	}

	pdf_drop_obj(obj);
}

static void writexref(pdf_document *xref, pdf_write_options *opts, int from, int to, int first, int main_xref_offset, int startxref)
{
	pdf_obj *trailer = NULL;
	pdf_obj *obj;
	pdf_obj *nobj = NULL;
	int num;
	fz_context *ctx = xref->ctx;

	fprintf(opts->out, "xref\n%d %d\n", from, to - from);
	opts->first_xref_entry_offset = ftell(opts->out);
	for (num = from; num < to; num++)
	{
		if (opts->use_list[num])
			fprintf(opts->out, "%010d %05d n \n", opts->ofs_list[num], opts->gen_list[num]);
		else
			fprintf(opts->out, "%010d %05d f \n", opts->ofs_list[num], opts->gen_list[num]);
	}
	fprintf(opts->out, "\n");

	fz_var(trailer);
	fz_var(nobj);

	fz_try(ctx)
	{
		trailer = pdf_new_dict(ctx, 5);

		nobj = pdf_new_int(ctx, to);
		pdf_dict_puts(trailer, "Size", nobj);
		pdf_drop_obj(nobj);
		nobj = NULL;

		if (first)
		{
			obj = pdf_dict_gets(xref->trailer, "Info");
			if (obj)
				pdf_dict_puts(trailer, "Info", obj);

			obj = pdf_dict_gets(xref->trailer, "Root");
			if (obj)
				pdf_dict_puts(trailer, "Root", obj);

			obj = pdf_dict_gets(xref->trailer, "ID");
			if (obj)
				pdf_dict_puts(trailer, "ID", obj);
		}
		if (main_xref_offset != 0)
		{
			nobj = pdf_new_int(ctx, main_xref_offset);
			pdf_dict_puts(trailer, "Prev", nobj);
			pdf_drop_obj(nobj);
			nobj = NULL;
		}
	}
	fz_always(ctx)
	{
		pdf_drop_obj(nobj);
	}
	fz_catch(ctx)
	{
		fz_rethrow(ctx);
	}

	fprintf(opts->out, "trailer\n");
	pdf_fprint_obj(opts->out, trailer, opts->do_expand == 0);
	fprintf(opts->out, "\n");

	pdf_drop_obj(trailer);

	fprintf(opts->out, "startxref\n%d\n%%%%EOF\n", startxref);
}

static void
padto(FILE *file, int target)
{
	int pos = ftell(file);

	assert(pos <= target);
	while (pos < target)
	{
		fputc('\n', file);
		pos++;
	}
}

static void
dowriteobject(pdf_document *xref, pdf_write_options *opts, int num, int pass)
{
	if (xref->table[num].type == 'f')
		opts->gen_list[num] = xref->table[num].gen;
	if (xref->table[num].type == 'n')
		opts->gen_list[num] = xref->table[num].gen;
	if (xref->table[num].type == 'o')
		opts->gen_list[num] = 0;

	if (opts->do_garbage && !opts->use_list[num])
		return;

	if (xref->table[num].type == 'n' || xref->table[num].type == 'o')
	{
		if (pass > 0)
			padto(opts->out, opts->ofs_list[num]);
		opts->ofs_list[num] = ftell(opts->out);
		writeobject(xref, opts, num, opts->gen_list[num]);
	}
	else
		opts->use_list[num] = 0;
}

static void
writeobjects(pdf_document *xref, pdf_write_options *opts, int pass)
{
	int num;

	fprintf(opts->out, "%%PDF-%d.%d\n", xref->version / 10, xref->version % 10);
	fprintf(opts->out, "%%\316\274\341\277\246\n\n");

	dowriteobject(xref, opts, opts->start, pass);

	if (opts->do_linear)
	{
		/* Write first xref */
		if (pass == 0)
			opts->first_xref_offset = ftell(opts->out);
		else
			padto(opts->out, opts->first_xref_offset);
		writexref(xref, opts, opts->start, xref->len, 1, opts->main_xref_offset, 0);
	}

	for (num = opts->start+1; num < xref->len; num++)
		dowriteobject(xref, opts, num, pass);
	if (opts->do_linear && pass == 1)
	{
		int offset = (opts->start == 1 ? opts->main_xref_offset : opts->ofs_list[1] + opts->hintstream_len);
		padto(opts->out, offset);
	}
	for (num = 1; num < opts->start; num++)
	{
		if (pass == 1)
			opts->ofs_list[num] += opts->hintstream_len;
		dowriteobject(xref, opts, num, pass);
	}
}

static int
my_log2(int x)
{
	int i = 0;

	if (x <= 0)
		return 0;

	while ((1<<i) <= x && (1<<i) > 0)
		i++;

	if ((1<<i) <= 0)
		return 0;

	return i;
}

static void
make_page_offset_hints(pdf_document *xref, pdf_write_options *opts, fz_buffer *buf)
{
	fz_context *ctx = xref->ctx;
	int i, j;
	int min_objs_per_page, max_objs_per_page;
	int min_page_length, max_page_length;
	int objs_per_page_bits;
	int min_shared_object, max_shared_object;
	int max_shared_object_refs;
	int min_shared_length, max_shared_length;
	page_objects **pop = &opts->page_object_lists->page[0];
	int page_len_bits, shared_object_bits, shared_object_id_bits;
	int shared_length_bits;

	min_shared_object = xref->len;
	max_shared_object = 1;
	min_shared_length = opts->file_len;
	max_shared_length = 0;
	for (i=1; i < xref->len; i++)
	{
		int min, max, page;

		min = opts->ofs_list[i];
		if (i == opts->start-1 || (opts->start == 1 && i == xref->len-1))
			max = opts->main_xref_offset;
		else if (i == xref->len-1)
			max = opts->ofs_list[1];
		else
			max = opts->ofs_list[i+1];

		assert(max > min);

		if (opts->use_list[i] & USE_SHARED)
		{
			page = -1;
			if (i < min_shared_object)
				min_shared_object = i;
			if (i > max_shared_object)
				max_shared_object = i;
			if (min_shared_length > max - min)
				min_shared_length = max - min;
			if (max_shared_length < max - min)
				max_shared_length = max - min;
		}
		else if (opts->use_list[i] & (USE_CATALOGUE | USE_HINTS | USE_PARAMS))
			page = -1;
		else if (opts->use_list[i] & USE_PAGE1)
		{
			page = 0;
			if (min_shared_length > max - min)
				min_shared_length = max - min;
			if (max_shared_length < max - min)
				max_shared_length = max - min;
		}
		else if (opts->use_list[i] == 0)
			page = -1;
		else
			page = opts->use_list[i]>>USE_PAGE_SHIFT;

		if (page >= 0)
		{
			pop[page]->num_objects++;
			if (pop[page]->min_ofs > min)
				pop[page]->min_ofs = min;
			if (pop[page]->max_ofs < max)
				pop[page]->max_ofs = max;
		}
	}

	min_objs_per_page = max_objs_per_page = pop[0]->num_objects;
	min_page_length = max_page_length = pop[0]->max_ofs - pop[0]->min_ofs;
	for (i=1; i < opts->page_count; i++)
	{
		int tmp;
		if (min_objs_per_page > pop[i]->num_objects)
			min_objs_per_page = pop[i]->num_objects;
		if (max_objs_per_page < pop[i]->num_objects)
			max_objs_per_page = pop[i]->num_objects;
		tmp = pop[i]->max_ofs - pop[i]->min_ofs;
		if (tmp < min_page_length)
			min_page_length = tmp;
		if (tmp > max_page_length)
			max_page_length = tmp;
	}

	for (i=0; i < opts->page_count; i++)
	{
		int count = 0;
		int j;
		page_objects *po = opts->page_object_lists->page[i];
		for (j = 0; j < po->len; j++)
		{
			if (i == 0 && opts->use_list[po->object[j]] & USE_PAGE1)
				count++;
			else if (i != 0 && opts->use_list[po->object[j]] & USE_SHARED)
				count++;
		}
		po->num_shared = count;
		if (i == 0 || count > max_shared_object_refs)
			max_shared_object_refs = count;
	}
	if (min_shared_object > max_shared_object)
		min_shared_object = max_shared_object = 0;

	/* Table F.3 - Header */
	/* Header Item 1: Least number of objects in a page */
	fz_write_buffer_bits(ctx, buf, min_objs_per_page, 32);
	/* Header Item 2: Location of first pages page object */
	fz_write_buffer_bits(ctx, buf, opts->ofs_list[pop[0]->page_object_number], 32);
	/* Header Item 3: Number of bits required to represent the difference
	 * between the greatest and least number of objects in a page. */
	objs_per_page_bits = my_log2(max_objs_per_page - min_objs_per_page);
	fz_write_buffer_bits(ctx, buf, objs_per_page_bits, 16);
	/* Header Item 4: Least length of a page. */
	fz_write_buffer_bits(ctx, buf, min_page_length, 32);
	/* Header Item 5: Number of bits needed to represent the difference
	 * between the greatest and least length of a page. */
	page_len_bits = my_log2(max_page_length - min_page_length);
	fz_write_buffer_bits(ctx, buf, page_len_bits, 16);
	/* Header Item 6: Least offset to start of content stream (Acrobat
	 * sets this to always be 0) */
	fz_write_buffer_bits(ctx, buf, 0, 32);
	/* Header Item 7: Number of bits needed to represent the difference
	 * between the greatest and least offset to content stream (Acrobat
	 * sets this to always be 0) */
	fz_write_buffer_bits(ctx, buf, 0, 16);
	/* Header Item 8: Least content stream length. (Acrobat
	 * sets this to always be 0) */
	fz_write_buffer_bits(ctx, buf, 0, 32);
	/* Header Item 9: Number of bits needed to represent the difference
	 * between the greatest and least content stream length (Acrobat
	 * sets this to always be the same as item 5) */
	fz_write_buffer_bits(ctx, buf, page_len_bits, 16);
	/* Header Item 10: Number of bits needed to represent the greatest
	 * number of shared object references. */
	shared_object_bits = my_log2(max_shared_object_refs);
	fz_write_buffer_bits(ctx, buf, shared_object_bits, 16);
	/* Header Item 11: Number of bits needed to represent the greatest
	 * shared object identifier. */
	shared_object_id_bits = my_log2(max_shared_object - min_shared_object + pop[0]->num_shared);
	fz_write_buffer_bits(ctx, buf, shared_object_id_bits, 16);
	/* Header Item 12: Number of bits needed to represent the numerator
	 * of the fractions. We always send 0. */
	fz_write_buffer_bits(ctx, buf, 0, 16);
	/* Header Item 13: Number of bits needed to represent the denominator
	 * of the fractions. We always send 0. */
	fz_write_buffer_bits(ctx, buf, 0, 16);

	/* Table F.4 - Page offset hint table (per page) */
	/* Item 1: A number that, when added to the least number of objects
	 * on a page, gives the number of objects in the page. */
	for (i = 0; i < opts->page_count; i++)
	{
		fz_write_buffer_bits(ctx, buf, pop[i]->num_objects - min_objs_per_page, objs_per_page_bits);
	}
	fz_write_buffer_pad(ctx, buf);
	/* Item 2: A number that, when added to the least page length, gives
	 * the length of the page in bytes. */
	for (i = 0; i < opts->page_count; i++)
	{
		fz_write_buffer_bits(ctx, buf, pop[i]->max_ofs - pop[i]->min_ofs - min_page_length, page_len_bits);
	}
	fz_write_buffer_pad(ctx, buf);
	/* Item 3: The number of shared objects referenced from the page. */
	for (i = 0; i < opts->page_count; i++)
	{
		fz_write_buffer_bits(ctx, buf, pop[i]->num_shared, shared_object_bits);
	}
	fz_write_buffer_pad(ctx, buf);
	/* Item 4: Shared object id for each shared object ref in every page.
	 * Spec says "not for page 1", but acrobat does send page 1's - all
	 * as zeros. */
	for (i = 0; i < opts->page_count; i++)
	{
		for (j = 0; j < pop[i]->len; j++)
		{
			int o = pop[i]->object[j];
			if (i == 0 && opts->use_list[o] & USE_PAGE1)
				fz_write_buffer_bits(ctx, buf, 0 /* o - pop[0]->page_object_number */, shared_object_id_bits);
			if (i != 0 && opts->use_list[o] & USE_SHARED)
				fz_write_buffer_bits(ctx, buf, o - min_shared_object + pop[0]->num_shared, shared_object_id_bits);
		}
	}
	fz_write_buffer_pad(ctx, buf);
	/* Item 5: Numerator of fractional position for each shared object reference. */
	/* We always send 0 in 0 bits */
	/* Item 6: A number that, when added to the least offset to the start
	 * of the content stream (F.3 Item 6), gives the offset in bytes of
	 * start of the pages content stream object relative to the beginning
	 * of the page. Always 0 in 0 bits. */
	/* Item 7: A number that, when added to the least content stream length
	 * (F.3 Item 8), gives the length of the pages content stream object.
	 * Always == Item 2 as least content stream length = least page stream
	 * length.
	 */
	for (i = 0; i < opts->page_count; i++)
	{
		fz_write_buffer_bits(ctx, buf, pop[i]->max_ofs - pop[i]->min_ofs - min_page_length, page_len_bits);
	}

	/* Pad, and then do shared object hint table */
	fz_write_buffer_pad(ctx, buf);
	opts->hints_shared_offset = buf->len;

	/* Table F.5: */
	/* Header Item 1: Object number of the first object in the shared
	 * objects section. */
	fz_write_buffer_bits(ctx, buf, min_shared_object, 32);
	/* Header Item 2: Location of first object in the shared objects
	 * section. */
	fz_write_buffer_bits(ctx, buf, opts->ofs_list[min_shared_object], 32);
	/* Header Item 3: The number of shared object entries for the first
	 * page. */
	fz_write_buffer_bits(ctx, buf, pop[0]->num_shared, 32);
	/* Header Item 4: The number of shared object entries for the shared
	 * objects section + first page. */
	fz_write_buffer_bits(ctx, buf, max_shared_object - min_shared_object + pop[0]->num_shared, 32);
	/* Header Item 5: The number of bits needed to represent the greatest
	 * number of objects in a shared object group (Always 0). */
	fz_write_buffer_bits(ctx, buf, 0, 16);
	/* Header Item 6: The least length of a shared object group in bytes. */
	fz_write_buffer_bits(ctx, buf, min_shared_length, 32);
	/* Header Item 7: The number of bits required to represent the
	 * difference between the greatest and least length of a shared object
	 * group. */
	shared_length_bits = my_log2(max_shared_length - min_shared_length);
	fz_write_buffer_bits(ctx, buf, shared_length_bits, 16);

	/* Table F.6 */
	/* Item 1: Shared object group length (page 1 objects) */
	for (j = 0; j < pop[0]->len; j++)
	{
		int o = pop[0]->object[j];
		int min, max;
		min = opts->ofs_list[o];
		if (o == opts->start-1)
			max = opts->main_xref_offset;
		else if (o < xref->len-1)
			max = opts->ofs_list[o+1];
		else
			max = opts->ofs_list[1];
		if (opts->use_list[o] & USE_PAGE1)
			fz_write_buffer_bits(ctx, buf, max - min - min_shared_length, shared_length_bits);
	}
	/* Item 1: Shared object group length (shared objects) */
	for (i = min_shared_object; i <= max_shared_object; i++)
	{
		int min, max;
		min = opts->ofs_list[i];
		if (i == opts->start-1)
			max = opts->main_xref_offset;
		else if (i < xref->len-1)
			max = opts->ofs_list[i+1];
		else
			max = opts->ofs_list[1];
		fz_write_buffer_bits(ctx, buf, max - min - min_shared_length, shared_length_bits);
	}
	fz_write_buffer_pad(ctx, buf);

	/* Item 2: MD5 presence flags */
	for (i = max_shared_object - min_shared_object + pop[0]->num_shared; i > 0; i--)
	{
		fz_write_buffer_bits(ctx, buf, 0, 1);
	}
	fz_write_buffer_pad(ctx, buf);
	/* Item 3: MD5 sums (not present) */
	fz_write_buffer_pad(ctx, buf);
	/* Item 4: Number of objects in the group (not present) */
}

static void
make_hint_stream(pdf_document *xref, pdf_write_options *opts)
{
	fz_context *ctx = xref->ctx;
	fz_buffer *buf = fz_new_buffer(ctx, 100);

	fz_try(ctx)
	{
		make_page_offset_hints(xref, opts, buf);
		pdf_update_stream(xref, xref->len-1, buf);
		opts->hintstream_len = buf->len;
		fz_drop_buffer(ctx, buf);
	}
	fz_catch(ctx)
	{
		fz_drop_buffer(ctx, buf);
		fz_rethrow(ctx);
	}
}

#ifdef DEBUG_WRITING
static void dump_object_details(pdf_document *xref, pdf_write_options *opts)
{
	int i;

	for (i = 0; i < xref->len; i++)
	{
		fprintf(stderr, "%d@%d: use=%d\n", i, opts->ofs_list[i], opts->use_list[i]);
	}
}
#endif


void pdf_write_document(pdf_document *xref, char *filename, fz_write_options *fz_opts)
{
	int lastfree;
	int num;
	pdf_write_options opts = { 0 };
	fz_context *ctx;

	if (!xref || !fz_opts)
		return;

	ctx = xref->ctx;

	opts.out = fopen(filename, "wb");
	if (!opts.out)
		fz_throw(ctx, "cannot open output file '%s'", filename);

	fz_try(ctx)
	{
		opts.do_expand = fz_opts ? fz_opts->do_expand : 0;
		opts.do_garbage = fz_opts ? fz_opts->do_garbage : 0;
		opts.do_ascii = fz_opts ? fz_opts->do_ascii: 0;
		opts.do_linear = fz_opts ? fz_opts->do_linear: 0;
		opts.start = 0;
		opts.main_xref_offset = INT_MIN;
		/* We deliberately make these arrays long enough to cope with
		 * 1 to n access rather than 0..n-1, and add space for 2 new
		 * extra entries that may be required for linearization. */
		opts.use_list = fz_malloc_array(ctx, xref->len + 3, sizeof(int));
		opts.ofs_list = fz_malloc_array(ctx, xref->len + 3, sizeof(int));
		opts.gen_list = fz_calloc(ctx, xref->len + 3, sizeof(int));
		opts.renumber_map = fz_malloc_array(ctx, xref->len + 3, sizeof(int));
		opts.rev_renumber_map = fz_malloc_array(ctx, xref->len + 3, sizeof(int));
		opts.rev_gen_list = fz_malloc_array(ctx, xref->len + 3, sizeof(int));

		for (num = 0; num < xref->len; num++)
		{
			opts.use_list[num] = 0;
			opts.ofs_list[num] = 0;
			opts.renumber_map[num] = num;
			opts.rev_renumber_map[num] = num;
			opts.rev_gen_list[num] = xref->table[num].gen;
		}

		/* Make sure any objects hidden in compressed streams have been loaded */
		preloadobjstms(xref);

		/* Sweep & mark objects from the trailer */
		if (opts.do_garbage >= 1)
			sweepobj(xref, &opts, xref->trailer);
		else
			for (num = 0; num < xref->len; num++)
				opts.use_list[num] = 1;

		/* Coalesce and renumber duplicate objects */
		if (opts.do_garbage >= 3)
			removeduplicateobjs(xref, &opts);

		/* Compact xref by renumbering and removing unused objects */
		if (opts.do_garbage >= 2 || opts.do_linear)
			compactxref(xref, &opts);

		/* Make renumbering affect all indirect references and update xref */
		if (opts.do_garbage >= 2 || opts.do_linear)
			renumberobjs(xref, &opts);

		if (opts.do_linear)
		{
			linearize(xref, &opts);
		}

		writeobjects(xref, &opts, 0);

#ifdef DEBUG_WRITING
		dump_object_details(xref, &opts);
#endif

		/* Construct linked list of free object slots */
		lastfree = 0;
		for (num = 0; num < xref->len; num++)
		{
			if (!opts.use_list[num])
			{
				opts.gen_list[num]++;
				opts.ofs_list[lastfree] = num;
				lastfree = num;
			}
		}

		if (opts.do_linear)
		{
			opts.main_xref_offset = ftell(opts.out);
			writexref(xref, &opts, 0, opts.start, 0, 0, opts.first_xref_offset);
			opts.file_len = ftell(opts.out);

			make_hint_stream(xref, &opts);
			opts.file_len += opts.hintstream_len;
			opts.main_xref_offset += opts.hintstream_len;
			update_linearization_params(xref, &opts);
			fseek(opts.out, 0, 0);
			writeobjects(xref, &opts, 1);

			padto(opts.out, opts.main_xref_offset);
			writexref(xref, &opts, 0, opts.start, 0, 0, opts.first_xref_offset);
		}
		else
		{
			opts.first_xref_offset = ftell(opts.out);
			writexref(xref, &opts, 0, xref->len, 1, 0, opts.first_xref_offset);
		}

		xref->dirty = 0;
	}
	fz_always(ctx)
	{
#ifdef DEBUG_LINEARIZATION
		page_objects_dump(&opts);
		objects_dump(xref, &opts);
#endif
		fz_free(ctx, opts.use_list);
		fz_free(ctx, opts.ofs_list);
		fz_free(ctx, opts.gen_list);
		fz_free(ctx, opts.renumber_map);
		fz_free(ctx, opts.rev_renumber_map);
		fz_free(ctx, opts.rev_gen_list);
		pdf_drop_obj(opts.linear_l);
		pdf_drop_obj(opts.linear_h0);
		pdf_drop_obj(opts.linear_h1);
		pdf_drop_obj(opts.linear_o);
		pdf_drop_obj(opts.linear_e);
		pdf_drop_obj(opts.linear_n);
		pdf_drop_obj(opts.linear_t);
		pdf_drop_obj(opts.hints_s);
		pdf_drop_obj(opts.hints_length);
		page_objects_list_destroy(ctx, opts.page_object_lists);
		fclose(opts.out);
	}
	fz_catch(ctx)
	{
		fz_rethrow(ctx);
	}
}
