static void
pdf_load_name_tree_imp(pdf_obj *dict, pdf_document *xref, pdf_obj *node)
{
	fz_context *ctx = xref->ctx;
	pdf_obj *kids = pdf_dict_gets(node, "Kids");
	pdf_obj *names = pdf_dict_gets(node, "Names");
	int i;

	if (kids && !pdf_dict_mark(node))
	{
		for (i = 0; i < pdf_array_len(kids); i++)
			pdf_load_name_tree_imp(dict, xref, pdf_array_get(kids, i));
		pdf_dict_unmark(node);
	}

	if (names)
	{
		for (i = 0; i + 1 < pdf_array_len(names); i += 2)
		{
			pdf_obj *key = pdf_array_get(names, i);
			pdf_obj *val = pdf_array_get(names, i + 1);
			if (pdf_is_string(key))
			{
				key = pdf_to_utf8_name(ctx, key);
				pdf_dict_put(dict, key, val);
				pdf_drop_obj(key);
			}
			else if (pdf_is_name(key))
			{
				pdf_dict_put(dict, key, val);
			}
		}
	}
}

/* returns the number of attachments saved */
int save_attachments(int pageno, char *targetdir)
{
	pdf_page *page = pdf_load_page(doc, pageno-1);
	pdf_annot *annot;
	int saved_count = 0;

	for (annot = page->annots; annot ; annot = annot->next) {
		pdf_obj *fs_obj = pdf_dict_gets(annot->obj, "FS");
		if (fs_obj) {
			pdf_obj *ef_obj;
			char *name = basename(strdup(pdf_to_str_buf(pdf_dict_gets(fs_obj, "F"))));
			ef_obj = pdf_dict_gets(fs_obj, "EF");
			if (ef_obj) {
				pdf_obj *f_obj = pdf_dict_gets(ef_obj, "F");
				if (f_obj && pdf_is_indirect(f_obj)) {
					static char pathname[PATH_MAX];
					sprintf(pathname, "%s/%s", targetdir, name);
					FILE *fout = fopen(pathname, "w");
					if (!fout) {
						fprintf(stderr, "extr: cannot write to file %s\n", pathname);
						exit(1);
					}
					dump_stream(pdf_to_num(f_obj), fout);
					fclose(fout);
					saved_count++;
				}
			}
		}
	}
	return saved_count;
}

static pdf_font_desc *
pdf_load_type0_font(pdf_document *xref, pdf_obj *dict)
{
	pdf_obj *dfonts;
	pdf_obj *dfont;
	pdf_obj *subtype;
	pdf_obj *encoding;
	pdf_obj *to_unicode;

	dfonts = pdf_dict_gets(dict, "DescendantFonts");
	if (!dfonts)
		fz_throw(xref->ctx, "cid font is missing descendant fonts");

	dfont = pdf_array_get(dfonts, 0);

	subtype = pdf_dict_gets(dfont, "Subtype");
	encoding = pdf_dict_gets(dict, "Encoding");
	to_unicode = pdf_dict_gets(dict, "ToUnicode");

	if (pdf_is_name(subtype) && !strcmp(pdf_to_name(subtype), "CIDFontType0"))
		return load_cid_font(xref, dfont, encoding, to_unicode);
	else if (pdf_is_name(subtype) && !strcmp(pdf_to_name(subtype), "CIDFontType2"))
		return load_cid_font(xref, dfont, encoding, to_unicode);
	else
		fz_throw(xref->ctx, "syntaxerror: unknown cid font type");

	return NULL; /* Stupid MSVC */
}

static fz_colorspace *
load_icc_based(pdf_document *doc, pdf_obj *dict)
{
	int n;

	n = pdf_to_int(pdf_dict_gets(dict, "N"));

	/* SumatraPDF: support alternate colorspaces for ICCBased */
	if (pdf_dict_gets(dict, "Alternate"))
	{
		fz_colorspace *cs_alt = pdf_load_colorspace(doc, pdf_dict_gets(dict, "Alternate"));
		if (cs_alt->n != n)
		{
			fz_drop_colorspace(doc->ctx, cs_alt);
			fz_throw(doc->ctx, FZ_ERROR_GENERIC, "ICCBased /Alternate colorspace must have %d components (not %d)", n, cs_alt->n);
		}
		return cs_alt;
	}

	switch (n)
	{
	case 1: return fz_device_gray(doc->ctx);
	case 3: return fz_device_rgb(doc->ctx);
	case 4: return fz_device_cmyk(doc->ctx);
	}

	fz_throw(doc->ctx, FZ_ERROR_GENERIC, "syntaxerror: ICCBased must have 1, 3 or 4 components");
	return NULL; /* Stupid MSVC */
}

static void
pdf_load_linear_shading(fz_context *ctx, pdf_document *doc, fz_shade *shade, pdf_obj *dict, int funcs, fz_function **func)
{
	pdf_obj *obj;
	float d0, d1;
	int e0, e1;

	obj = pdf_dict_gets(ctx, dict, "Coords");
	shade->u.l_or_r.coords[0][0] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 0));
	shade->u.l_or_r.coords[0][1] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 1));
	shade->u.l_or_r.coords[1][0] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 2));
	shade->u.l_or_r.coords[1][1] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 3));

	d0 = 0;
	d1 = 1;
	obj = pdf_dict_gets(ctx, dict, "Domain");
	if (obj)
	{
		d0 = pdf_to_real(ctx, pdf_array_get(ctx, obj, 0));
		d1 = pdf_to_real(ctx, pdf_array_get(ctx, obj, 1));
	}

	e0 = e1 = 0;
	obj = pdf_dict_gets(ctx, dict, "Extend");
	if (obj)
	{
		e0 = pdf_to_bool(ctx, pdf_array_get(ctx, obj, 0));
		e1 = pdf_to_bool(ctx, pdf_array_get(ctx, obj, 1));
	}

	pdf_sample_shade_function(ctx, shade, funcs, func, d0, d1);

	shade->u.l_or_r.extend[0] = e0;
	shade->u.l_or_r.extend[1] = e1;
}

static void execute_action(pdf_document *doc, pdf_obj *obj, pdf_obj *a)
{
	fz_context *ctx = doc->ctx;
	if (a)
	{
		char *type = pdf_to_name(pdf_dict_gets(a, "S"));

		if (!strcmp(type, "JavaScript"))
		{
			pdf_obj *js = pdf_dict_gets(a, "JS");
			if (js)
			{
				char *code = pdf_to_utf8(doc, js);
				fz_try(ctx)
				{
					pdf_js_execute(doc->js, code);
				}
				fz_always(ctx)
				{
					fz_free(ctx, code);
				}
				fz_catch(ctx)
				{
					fz_rethrow(ctx);
				}
			}
		}
		else if (!strcmp(type, "ResetForm"))

static int find_destination_pages(fz_context *ctx, pdf_obj *current, int page_num, pdf_obj **dest_pages, int *index)
{
	if(!strcmp(pdf_to_name(ctx, pdf_dict_gets(ctx, current, "Type")), "Page")) {
		return(--page_num);
	} if(!strcmp(pdf_to_name(ctx, pdf_dict_gets(ctx, current, "Type")), "Pages")) {
		pdf_obj *kids = pdf_dict_gets(ctx, current, "Kids");
		pdf_obj *count_obj = pdf_dict_gets(ctx, current, "Count");
		if(!pdf_is_array(ctx, kids) || !pdf_is_int(ctx, count_obj))
			return(-2);

		int count = pdf_to_int(ctx, count_obj);
		int i;
		for(i = 0; i < count; i++) {
			pdf_obj *current_kid = pdf_array_get(ctx, kids, i);

			page_num = find_destination_pages(ctx, current_kid, page_num, dest_pages, index);
			if(page_num == -1) {
				*index = i;
				*dest_pages = current;
				return(-2);
			} else if(page_num == -2) {
				return(-2); // just return, preserve index and dest_pages
			}
		}

		return(page_num);
	}

	return(page_num);
}

/* Find the point in a field hierarchy where all descendents
 * share the same name */
static pdf_obj *find_head_of_field_group(pdf_obj *obj)
{
	if (obj == NULL || pdf_dict_gets(obj, "T"))
		return obj;
	else
		return find_head_of_field_group(pdf_dict_gets(obj, "Parent"));
}

pdf_obj *
pdf_lookup_dest(pdf_document *xref, pdf_obj *needle)
{
	fz_context *ctx = xref->ctx;

	pdf_obj *root = pdf_dict_gets(xref->trailer, "Root");
	pdf_obj *dests = pdf_dict_gets(root, "Dests");
	pdf_obj *names = pdf_dict_gets(root, "Names");
	pdf_obj *dest = NULL;

	/* PDF 1.1 has destinations in a dictionary */
	if (dests)
	{
		if (pdf_is_name(needle))
			return pdf_dict_get(dests, needle);
		else
			return pdf_dict_gets(dests, pdf_to_str_buf(needle));
	}

	/* PDF 1.2 has destinations in a name tree */
	if (names && !dest)
	{
		pdf_obj *tree = pdf_dict_gets(names, "Dests");
		return pdf_lookup_name_imp(ctx, tree, needle);
	}

	return NULL;
}

void
pdf_update_annot(pdf_document *doc, pdf_annot *annot)
{
	/* SumatraPDF: prevent regressions */
#if 0
	pdf_obj *obj, *ap, *as, *n;
	fz_context *ctx = doc->ctx;

	if (doc->update_appearance)
		doc->update_appearance(doc, annot);

	obj = annot->obj;

	ap = pdf_dict_gets(obj, "AP");
	as = pdf_dict_gets(obj, "AS");

	if (pdf_is_dict(ap))
	{
		pdf_hotspot *hp = &doc->hotspot;

		n = NULL;

		if (hp->num == pdf_to_num(obj)
			&& hp->gen == pdf_to_gen(obj)
			&& (hp->state & HOTSPOT_POINTER_DOWN))
		{
			n = pdf_dict_gets(ap, "D"); /* down state */
		}

		if (n == NULL)
			n = pdf_dict_gets(ap, "N"); /* normal state */

		/* lookup current state in sub-dictionary */
		if (!pdf_is_stream(doc, pdf_to_num(n), pdf_to_gen(n)))
			n = pdf_dict_get(n, as);

		pdf_drop_xobject(ctx, annot->ap);
		annot->ap = NULL;

		if (pdf_is_stream(doc, pdf_to_num(n), pdf_to_gen(n)))
		{
			fz_try(ctx)
			{
				annot->ap = pdf_load_xobject(doc, n);
				pdf_transform_annot(annot);
				annot->ap_iteration = annot->ap->iteration;
			}
			fz_catch(ctx)
			{
				fz_rethrow_if(ctx, FZ_ERROR_TRYLATER);
				fz_warn(ctx, "ignoring broken annotation");
			}
		}
	}
#endif
}

void
pdf_insert_page(pdf_document *doc, pdf_page *page, int at)
{
	fz_context *ctx = doc->ctx;
	int count = pdf_count_pages(doc);
	pdf_obj *parent, *kids;
	pdf_obj *page_ref;
	int i;

	page_ref = pdf_new_ref(doc, page->me);

	fz_try(ctx)
	{
		if (count == 0)
		{
			/* TODO: create new page tree? */
			fz_throw(ctx, FZ_ERROR_GENERIC, "empty page tree, cannot insert page");
		}
		else if (at >= count)
		{
			if (at > count)
				fz_throw(ctx, FZ_ERROR_GENERIC, "cannot insert page beyond end of page tree");

			/* append after last page */
			pdf_lookup_page_loc(doc, count - 1, &parent, &i);
			kids = pdf_dict_gets(parent, "Kids");
			pdf_array_insert(kids, page_ref, i + 1);
		}
		else
		{
			/* insert before found page */
			pdf_lookup_page_loc(doc, at, &parent, &i);
			kids = pdf_dict_gets(parent, "Kids");
			pdf_array_insert(kids, page_ref, i);
		}

		pdf_dict_puts(page->me, "Parent", parent);

		/* Adjust page counts */
		while (parent)
		{
			int count = pdf_to_int(pdf_dict_gets(parent, "Count"));
			pdf_dict_puts_drop(parent, "Count", pdf_new_int(doc, count + 1));
			parent = pdf_dict_gets(parent, "Parent");
		}

	}
	fz_always(ctx)
	{
		pdf_drop_obj(page_ref);
	}
	fz_catch(ctx)
	{
		fz_rethrow(ctx);
	}
}

pdf_obj *
pdf_lookup_name(pdf_document *xref, char *which, pdf_obj *needle)
{
	fz_context *ctx = xref->ctx;

	pdf_obj *root = pdf_dict_gets(xref->trailer, "Root");
	pdf_obj *names = pdf_dict_gets(root, "Names");
	pdf_obj *tree = pdf_dict_gets(names, which);
	return pdf_lookup_name_imp(ctx, tree, needle);
}

static int
pdf_pattern_uses_blending(pdf_document *doc, pdf_obj *dict)
{
	pdf_obj *obj;
	obj = pdf_dict_gets(dict, "Resources");
	if (pdf_resources_use_blending(doc, obj))
		return 1;
	obj = pdf_dict_gets(dict, "ExtGState");
	return pdf_extgstate_uses_blending(doc, obj);
}

static int
pdf_resources_use_blending(pdf_document *doc, pdf_obj *rdb)
{
	fz_context *ctx = doc->ctx;
	pdf_obj *obj;
	int i, n, useBM = 0;

	if (!rdb)
		return 0;

	/* Have we been here before and remembered an answer? */
	if (pdf_obj_memo(rdb, &useBM))
		return useBM;

	/* stop on cyclic resource dependencies */
	if (pdf_mark_obj(rdb))
		return 0;

	fz_try(ctx)
	{
		obj = pdf_dict_gets(rdb, "ExtGState");
		n = pdf_dict_len(obj);
		for (i = 0; i < n; i++)
			if (pdf_extgstate_uses_blending(doc, pdf_dict_get_val(obj, i)))
				goto found;

		obj = pdf_dict_gets(rdb, "Pattern");
		n = pdf_dict_len(obj);
		for (i = 0; i < n; i++)
			if (pdf_pattern_uses_blending(doc, pdf_dict_get_val(obj, i)))
				goto found;

		obj = pdf_dict_gets(rdb, "XObject");
		n = pdf_dict_len(obj);
		for (i = 0; i < n; i++)
			if (pdf_xobject_uses_blending(doc, pdf_dict_get_val(obj, i)))
				goto found;
		if (0)
		{
found:
			useBM = 1;
		}
	}
	fz_always(ctx)
	{
		pdf_unmark_obj(rdb);
	}
	fz_catch(ctx)
	{
		fz_rethrow(ctx);
	}

	pdf_set_obj_memo(rdb, useBM);
	return useBM;
}

pdf_obj *
pdf_lookup_page_loc(pdf_document *doc, int needle, pdf_obj **parentp, int *indexp)
{
	pdf_obj *root = pdf_dict_gets(pdf_trailer(doc), "Root");
	pdf_obj *node = pdf_dict_gets(root, "Pages");
	int skip = needle;
	pdf_obj *hit = pdf_lookup_page_loc_imp(doc, node, &skip, parentp, indexp);
	if (!hit)
		fz_throw(doc->ctx, FZ_ERROR_GENERIC, "cannot find page %d in page tree", needle);
	return hit;
}

ErrorCode juggler_add_pages_from_file(juggler_t *dest, juggler_t *src, int dest_index)
{
	pdf_obj *dest_pages = pdf_dict_getp(dest->ctx, 
		pdf_trailer(dest->ctx, dest->pdf), "Root/Pages");
	int dest_pages_index = pdf_array_len(dest->ctx, 
		pdf_dict_gets(dest->ctx, dest_pages, "Kids"));
		
	/* be aware that this function does not change the two variables if the page
	   index is greater than the number of pages */
	find_destination_pages(dest->ctx, 
		dest_pages, dest_index, &dest_pages, &dest_pages_index);

	pdf_obj *dest_kids = pdf_dict_gets(dest->ctx, dest_pages, "Kids");
	if(!pdf_is_indirect(dest->ctx, dest_pages) || 
		!pdf_is_dict(dest->ctx, dest_pages) || !pdf_is_array(dest->ctx, dest_kids))
	{
		return(ERROR_INVALID_RANGE);
	}
	
	pdf_obj *pages_root = pdf_dict_getp(src->ctx, pdf_trailer(src->ctx, src->pdf), "Root/Pages");
	if(!pdf_is_indirect(src->ctx, pages_root) || !pdf_is_dict(src->ctx, pages_root))
		return(ERROR_NO_PAGES);

	/* if we copy the root pages-node and it's referenced objects, we will copy 
	   all pages and all objects those pages need */
	pdf_obj *new_pages_ref = copy_object_single(dest->ctx, dest->pdf, src->ctx, src->pdf, pages_root);

	/* insert new pages-node */
	pdf_array_insert_drop(dest->ctx, dest_kids, new_pages_ref, dest_pages_index);

	/* update the parent */
	pdf_obj *new_pages_parent = pdf_new_indirect(dest->ctx, dest->pdf, 
		pdf_to_num(dest->ctx, dest_pages), pdf_to_gen(dest->ctx, dest_pages));
	pdf_dict_puts_drop(dest->ctx, new_pages_ref, "Parent", new_pages_parent);

	/* TODO: If dest_pages contains anything inheritable but not the new node
	         we need to insert empty items to prevent this inerhitance */

	/* update count */
	int new_count = pdf_to_int(dest->ctx, 
		pdf_dict_gets(dest->ctx, dest_pages, "Count")) + src->pagecount;
	pdf_dict_puts_drop(dest->ctx, dest_pages, "Count", 
		pdf_new_int(dest->ctx, dest->pdf, new_count));

	/* let MuPDF rebuild the page tree */
	pdf_finish_edit(dest->ctx, dest->pdf);
	dest->pdf->page_count = new_count;

	/* update juggler's state */
	juggler_page_tree_changed_due_to_insert(dest, dest_index, src->pagecount);

	return(NoError);
}

static void
gatherforms(int page, pdf_obj *pageref, pdf_obj *pageobj, pdf_obj *dict)
{
	int i, n;

	n = pdf_dict_len(dict);
	for (i = 0; i < n; i++)
	{
		pdf_obj *xobjdict;
		pdf_obj *type;
		pdf_obj *subtype;
		pdf_obj *group;
		pdf_obj *groupsubtype;
		pdf_obj *reference;
		int k;

		xobjdict = pdf_dict_get_val(dict, i);
		if (!pdf_is_dict(xobjdict))
		{
			fz_warn(ctx, "not a xobject dict (%d %d R)", pdf_to_num(xobjdict), pdf_to_gen(xobjdict));
			continue;
		}

		type = pdf_dict_gets(xobjdict, "Subtype");
		if (strcmp(pdf_to_name(type), "Form"))
			continue;

		subtype = pdf_dict_gets(xobjdict, "Subtype2");
		if (!strcmp(pdf_to_name(subtype), "PS"))
			continue;

		group = pdf_dict_gets(xobjdict, "Group");
		groupsubtype = pdf_dict_gets(group, "S");
		reference = pdf_dict_gets(xobjdict, "Ref");

		for (k = 0; k < forms; k++)
			if (!pdf_objcmp(form[k].u.form.obj, xobjdict))
				break;

		if (k < forms)
			continue;

		form = fz_resize_array(ctx, form, forms+1, sizeof(struct info));
		forms++;

		form[forms - 1].page = page;
		form[forms - 1].pageref = pageref;
		form[forms - 1].pageobj = pageobj;
		form[forms - 1].u.form.obj = xobjdict;
		form[forms - 1].u.form.groupsubtype = groupsubtype;
		form[forms - 1].u.form.reference = reference;
	}
}

static void
pdf_load_radial_shading(fz_shade *shade, pdf_document *xref, pdf_obj *dict, int funcs, pdf_function **func)
{
	pdf_obj *obj;
	float d0, d1;
	int e0, e1;
	float x0, y0, r0, x1, y1, r1;
	struct vertex p1, p2;
	fz_context *ctx = xref->ctx;

	obj = pdf_dict_gets(dict, "Coords");
	x0 = pdf_to_real(pdf_array_get(obj, 0));
	y0 = pdf_to_real(pdf_array_get(obj, 1));
	r0 = pdf_to_real(pdf_array_get(obj, 2));
	x1 = pdf_to_real(pdf_array_get(obj, 3));
	y1 = pdf_to_real(pdf_array_get(obj, 4));
	r1 = pdf_to_real(pdf_array_get(obj, 5));

	d0 = 0;
	d1 = 1;
	obj = pdf_dict_gets(dict, "Domain");
	if (pdf_array_len(obj) == 2)
	{
		d0 = pdf_to_real(pdf_array_get(obj, 0));
		d1 = pdf_to_real(pdf_array_get(obj, 1));
	}

	e0 = e1 = 0;
	obj = pdf_dict_gets(dict, "Extend");
	if (pdf_array_len(obj) == 2)
	{
		e0 = pdf_to_bool(pdf_array_get(obj, 0));
		e1 = pdf_to_bool(pdf_array_get(obj, 1));
	}

	pdf_sample_shade_function(ctx, shade, funcs, func, d0, d1);

	shade->type = FZ_RADIAL;

	shade->extend[0] = e0;
	shade->extend[1] = e1;

	p1.x = x0;
	p1.y = y0;
	p1.c[0] = r0;
	pdf_add_vertex(ctx, shade, &p1);

	p2.x = x1;
	p2.y = y1;
	p2.c[0] = r1;
	pdf_add_vertex(ctx, shade, &p2);
}

fz_outline *
pdf_load_outline(pdf_document *xref)
{
	pdf_obj *root, *obj, *first;

	root = pdf_dict_gets(xref->trailer, "Root");
	obj = pdf_dict_gets(root, "Outlines");
	first = pdf_dict_gets(obj, "First");
	if (first)
		return pdf_load_outline_imp(xref, first);

	return NULL;
}

static void
pdf_load_function_based_shading(fz_shade *shade, pdf_document *xref, pdf_obj *dict, pdf_function *func)
{
	pdf_obj *obj;
	float x0, y0, x1, y1;
	float fv[2];
	fz_matrix matrix;
	int xx, yy;
	fz_context *ctx = xref->ctx;
	float *p;

	x0 = y0 = 0;
	x1 = y1 = 1;
	obj = pdf_dict_gets(dict, "Domain");
	if (obj)
	{
		x0 = pdf_to_real(pdf_array_get(obj, 0));
		x1 = pdf_to_real(pdf_array_get(obj, 1));
		y0 = pdf_to_real(pdf_array_get(obj, 2));
		y1 = pdf_to_real(pdf_array_get(obj, 3));
	}

	obj = pdf_dict_gets(dict, "Matrix");
	if (obj)
		pdf_to_matrix(ctx, obj, &matrix);
	else
		matrix = fz_identity;
	shade->u.f.matrix = matrix;
	shade->u.f.xdivs = FUNSEGS;
	shade->u.f.ydivs = FUNSEGS;
	shade->u.f.fn_vals = fz_malloc(ctx, (FUNSEGS+1)*(FUNSEGS+1)*shade->colorspace->n*sizeof(float));
	shade->u.f.domain[0][0] = x0;
	shade->u.f.domain[0][1] = y0;
	shade->u.f.domain[1][0] = x1;
	shade->u.f.domain[1][1] = y1;

	p = shade->u.f.fn_vals;
	for (yy = 0; yy <= FUNSEGS; yy++)
	{
		fv[1] = y0 + (y1 - y0) * yy / FUNSEGS;

		for (xx = 0; xx <= FUNSEGS; xx++)
		{
			fv[0] = x0 + (x1 - x0) * xx / FUNSEGS;

			pdf_eval_function(ctx, func, fv, 2, p, shade->colorspace->n);
			p += shade->colorspace->n;
		}
	}
}