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);
			}
		}
	}
}

static int
do_name_tree_map(fz_context *ctx, pdf_obj *tree, pdf_name_tree_map_fn *fn, void *arg)
{
	int i;
	int n = 0;
	int m = 0;

	fz_var(n);
	fz_var(m);

	if (pdf_mark_obj(ctx, tree))
		fz_throw(ctx, FZ_ERROR_GENERIC, "Recursive name tree!");

	fz_try(ctx)
	{
		pdf_obj *arr = pdf_dict_get(ctx, tree, PDF_NAME_Kids);
		n = pdf_array_len(ctx, arr);

		for (i = n; i > 0;)
		{
			i--;
			if (do_name_tree_map(ctx, pdf_array_get(ctx, arr, i), fn, arg))
			{
				pdf_array_delete(ctx, arr, i);
				n--;
			}
		}

		arr = pdf_dict_get(ctx, tree, PDF_NAME_Names);
		m = pdf_array_len(ctx, arr);

		if (m & 1)
			fz_throw(ctx, FZ_ERROR_GENERIC, "Malformed Names array");

		for (i = m; i > 0;)
		{
			i -= 2;
			if (fn(ctx, tree, pdf_array_get(ctx, arr, i), pdf_array_get(ctx, arr, i+1), arg))
			{
				pdf_array_delete(ctx, arr, i+1);
				pdf_array_delete(ctx, arr, i);
				m -= 2;
			}
		}
	}
	fz_always(ctx)
		pdf_unmark_obj(ctx, tree);
	fz_catch(ctx)
		fz_rethrow(ctx);

	return n == 0 && m == 0;
}

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);
}

static void
pdf_load_mesh_params(pdf_document *xref, pdf_obj *dict, struct mesh_params *p)
{
	pdf_obj *obj;
	int i, n;

	p->x0 = p->y0 = 0;
	p->x1 = p->y1 = 1;
	for (i = 0; i < FZ_MAX_COLORS; i++)
	{
		p->c0[i] = 0;
		p->c1[i] = 1;
	}

	p->vprow = pdf_to_int(pdf_dict_gets(dict, "VerticesPerRow"));
	p->bpflag = pdf_to_int(pdf_dict_gets(dict, "BitsPerFlag"));
	p->bpcoord = pdf_to_int(pdf_dict_gets(dict, "BitsPerCoordinate"));
	p->bpcomp = pdf_to_int(pdf_dict_gets(dict, "BitsPerComponent"));

	obj = pdf_dict_gets(dict, "Decode");
	if (pdf_array_len(obj) >= 6)
	{
		n = (pdf_array_len(obj) - 4) / 2;
		p->x0 = pdf_to_real(pdf_array_get(obj, 0));
		p->x1 = pdf_to_real(pdf_array_get(obj, 1));
		p->y0 = pdf_to_real(pdf_array_get(obj, 2));
		p->y1 = pdf_to_real(pdf_array_get(obj, 3));
		for (i = 0; i < n; i++)
		{
			p->c0[i] = pdf_to_real(pdf_array_get(obj, 4 + i * 2));
			p->c1[i] = pdf_to_real(pdf_array_get(obj, 5 + i * 2));
		}
	}

	if (p->vprow < 2)
		p->vprow = 2;

	if (p->bpflag != 2 && p->bpflag != 4 && p->bpflag != 8)
		p->bpflag = 8;

	if (p->bpcoord != 1 && p->bpcoord != 2 && p->bpcoord != 4 &&
		p->bpcoord != 8 && p->bpcoord != 12 && p->bpcoord != 16 &&
		p->bpcoord != 24 && p->bpcoord != 32)
		p->bpcoord = 8;

	if (p->bpcomp != 1 && p->bpcomp != 2 && p->bpcomp != 4 &&
		p->bpcomp != 8 && p->bpcomp != 12 && p->bpcomp != 16)
		p->bpcomp = 8;
}

pdf_obj *
pdf_copy_array(fz_context *ctx, pdf_obj *obj)
{
	pdf_document *doc;
	pdf_obj *arr;
	int i;
	int n;

	RESOLVE(obj);
	if (!OBJ_IS_ARRAY(obj))
		fz_throw(ctx, FZ_ERROR_GENERIC, "not an array (%s)", pdf_objkindstr(obj));

	doc = ARRAY(obj)->doc;

	n = pdf_array_len(ctx, obj);
	arr = pdf_new_array(ctx, doc, n);
	fz_try(ctx)
		for (i = 0; i < n; i++)
			pdf_array_push(ctx, arr, pdf_array_get(ctx, obj, i));
	fz_catch(ctx)
	{
		pdf_drop_obj(ctx, arr);
		fz_rethrow(ctx);
	}

	return arr;
}

fz_link *
pdf_load_link_annots(pdf_document *xref, pdf_obj *annots, fz_matrix page_ctm)
{
	fz_link *link, *head, *tail;
	pdf_obj *obj;
	int i, n;

	head = tail = NULL;
	link = NULL;

	n = pdf_array_len(annots);
	for (i = 0; i < n; i++)
	{
		obj = pdf_array_get(annots, i);
		link = pdf_load_link(xref, obj, page_ctm);
		if (link)
		{
			if (!head)
				head = tail = link;
			else
			{
				tail->next = link;
				tail = link;
			}
		}
	}

	return head;
}

static fz_stream *
pdf_open_object_array(fz_context *ctx, pdf_document *doc, pdf_obj *list)
{
	fz_stream *stm;
	int i, n;

	n = pdf_array_len(ctx, list);
	stm = fz_open_concat(ctx, n, 1);

	fz_var(i); /* Workaround Mac compiler bug */
	for (i = 0; i < n; i++)
	{
		pdf_obj *obj = pdf_array_get(ctx, list, i);
		fz_try(ctx)
		{
			fz_concat_push(ctx, stm, pdf_open_stream(ctx, doc, pdf_to_num(ctx, obj), pdf_to_gen(ctx, obj)));
		}
		fz_catch(ctx)
		{
			fz_rethrow_if(ctx, FZ_ERROR_TRYLATER);
			fz_warn(ctx, "cannot load content stream part %d/%d", i + 1, n);
			continue;
		}
	}

	return stm;
}

/*
 * Scan stream dictionary for an explicit /Crypt filter
 */
static int
pdf_stream_has_crypt(fz_context *ctx, pdf_obj *stm)
{
	pdf_obj *filters;
	pdf_obj *obj;
	int i;

	filters = pdf_dict_geta(ctx, stm, PDF_NAME_Filter, PDF_NAME_F);
	if (filters)
	{
		if (pdf_name_eq(ctx, filters, PDF_NAME_Crypt))
			return 1;
		if (pdf_is_array(ctx, filters))
		{
			int n = pdf_array_len(ctx, filters);
			for (i = 0; i < n; i++)
			{
				obj = pdf_array_get(ctx, filters, i);
				if (pdf_name_eq(ctx, obj, PDF_NAME_Crypt))
					return 1;
			}
		}
	}
	return 0;
}

/*
 * Build a chain of filters given filter names and param dicts.
 * If head is given, start filter chain with it.
 * Assume ownership of head.
 */
static fz_stream *
build_filter_chain(fz_context *ctx, fz_stream *chain, pdf_document *doc, pdf_obj *fs, pdf_obj *ps, int num, int gen, fz_compression_params *params)
{
	pdf_obj *f;
	pdf_obj *p;
	int i, n;

	fz_try(ctx)
	{
		n = pdf_array_len(ctx, fs);
		for (i = 0; i < n; i++)
		{
			fz_stream *chain2;

			f = pdf_array_get(ctx, fs, i);
			p = pdf_array_get(ctx, ps, i);
			chain2 = chain;
			chain = NULL;
			chain = build_filter(ctx, chain2, doc, f, p, num, gen, (i == n-1 ? params : NULL));
		}
	}
	fz_catch(ctx)
	{
		fz_drop_stream(ctx, chain);
		fz_rethrow(ctx);
	}

	return chain;
}

int adjust_bleed_clipping(fz_context *ctx, pdf_document *doc, pdf_page *page, struct pos_info *pos)
{
	/* We clip each page two times... The first clipping rectangle just 
	   prevents the page from drawing outside of its area on the sheet.
	   The second clipping is done here and clips out all those things that
	   are located outside the bleed-box (e. g. printer's marks). */
	pdf_obj *bleed_box = 
		juggler_lookup_inherited_page_item(ctx, doc, page->me, "BleedBox");

	/* if no bleeding-box exists, there is no need for the second clipping */
	if(bleed_box == NULL) {
		pos->bleed_clip_x = pos->bleed_clip_y = 
			pos->bleed_clip_width = pos->bleed_clip_height = 0.0;
		return(0);
	}

	if(!pdf_is_array(ctx, bleed_box) || pdf_array_len(ctx, bleed_box) != 4)
		return(-1);

	fz_rect bleed_rect;
	pdf_to_rect(ctx, bleed_box, &bleed_rect);

	pos->bleed_clip_x = bleed_rect.x0;
	pos->bleed_clip_y = bleed_rect.y0;
	pos->bleed_clip_width = bleed_rect.x1 - bleed_rect.x0;
	pos->bleed_clip_height = bleed_rect.y1 - bleed_rect.y0;

	return(0);
}

static void
pdf_write_strike_out_appearance(fz_context *ctx, pdf_annot *annot, fz_buffer *buf, fz_rect *rect)
{
	fz_point quad[4], a, b;
	float h;
	pdf_obj *qp;
	int i, n;

	pdf_write_stroke_color_appearance(ctx, annot, buf);

	qp = pdf_dict_get(ctx, annot->obj, PDF_NAME(QuadPoints));
	n = pdf_array_len(ctx, qp);
	if (n > 0)
	{
		*rect = fz_empty_rect;
		for (i = 0; i < n; i += 8)
		{
			/* Acrobat draws the line at 3/7 of the box width from the bottom
			 * of the box and 1/16 thick of the box width. */

			h = extract_quad(ctx, quad, qp, i);
			a = lerp_point(quad[LL], quad[UL], 3/7.0f);
			b = lerp_point(quad[LR], quad[UR], 3/7.0f);

			fz_append_printf(ctx, buf, "%g w\n", h/16);
			fz_append_printf(ctx, buf, "%g %g m\n", a.x, a.y);
			fz_append_printf(ctx, buf, "%g %g l\n", b.x, b.y);
			fz_append_printf(ctx, buf, "S\n");

			union_quad(rect, quad, h/16);
		}
	}
}

static void
pdf_annot_color_imp(fz_context *ctx, pdf_annot *annot, pdf_obj *key, int *n, float color[4])
{
	pdf_obj *obj = pdf_dict_get(ctx, annot->obj, key);
	*n = 0;
	if (pdf_is_array(ctx, obj))
	{
		switch (pdf_array_len(ctx, obj))
		{
		case 1:
			*n = 1;
			color[0] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 0));
			break;
		case 3:
			*n = 3;
			color[0] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 0));
			color[1] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 1));
			color[2] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 2));
			break;
		case 4:
			*n = 4;
			color[0] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 0));
			color[1] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 1));
			color[2] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 2));
			color[3] = pdf_to_real(ctx, pdf_array_get(ctx, obj, 3));
			break;
		}
	}
}

/*
 * Scan stream dictionary for an explicit /Crypt filter
 */
static int
pdf_stream_has_crypt(fz_context *ctx, pdf_obj *stm)
{
    pdf_obj *filters;
    pdf_obj *obj;
    int i;

    filters = pdf_dict_getsa(stm, "Filter", "F");
    if (filters)
    {
        if (!strcmp(pdf_to_name(filters), "Crypt"))
            return 1;
        if (pdf_is_array(filters))
        {
            int n = pdf_array_len(filters);
            for (i = 0; i < n; i++)
            {
                obj = pdf_array_get(filters, i);
                if (!strcmp(pdf_to_name(obj), "Crypt"))
                    return 1;
            }
        }
    }
    return 0;
}

static fz_stream *
pdf_open_object_array(pdf_document *xref, pdf_obj *list)
{
	int i, n;
	fz_context *ctx = xref->ctx;
	fz_stream *stm;

	n = pdf_array_len(list);
	stm = fz_open_concat(ctx, n, 1);

	fz_var(i); /* Workaround Mac compiler bug */
	for (i = 0; i < n; i++)
	{
		pdf_obj *obj = pdf_array_get(list, i);
		fz_try(ctx)
		{
			fz_concat_push(stm, pdf_open_stream(xref, pdf_to_num(obj), pdf_to_gen(obj)));
		}
		fz_catch(ctx)
		{
			fz_warn(ctx, "cannot load content stream part %d/%d", i + 1, n);
			continue;
		}
	}

	return stm;
}

int adjust_page_position(fz_context *ctx, pdf_document *doc, pdf_page *page, struct pos_info *pos)
{
	/* if page is rotated we must add this to the desired rotation of the page */
	pos->rotate = (pos->rotate + page->rotate) % 360;
	fz_matrix rotation_mtx; /* tranformation of the user-space due to the rotation */
	fz_rotate(&rotation_mtx, page->rotate);

	/* get the media-box (with rotation applied) */
	pdf_obj *media_box = juggler_lookup_inherited_page_item(ctx, doc, page->me, "MediaBox");
	if(!pdf_is_array(ctx, media_box) || pdf_array_len(ctx, media_box) != 4) 
		return(-1); /* the specification forces a valid media-box... */

	fz_rect media_rect;
	pdf_to_rect(ctx, media_box, &media_rect);
	fz_transform_rect(&media_rect, &rotation_mtx);

	/* get trim-box */
	pdf_obj *trim_box = juggler_lookup_inherited_page_item(ctx, doc, page->me, "TrimBox");
	if(trim_box == NULL)
		trim_box = media_box;
	if(!pdf_is_array(ctx, trim_box) || pdf_array_len(ctx, trim_box) != 4)
		return(-2);

	fz_rect trim_rect;
	pdf_to_rect(ctx, trim_box, &trim_rect);
	fz_transform_rect(&trim_rect, &rotation_mtx);
	// TODO: Take scale into account

	double available_width = pos->width;
	double available_height = pos->height;

	double page_width = trim_rect.x1 - trim_rect.x0;
	double page_height = trim_rect.y1 - trim_rect.y0;

	/* position the page in the middle of the destination area */
	pos->content_translate_x = 
		media_rect.x0 - trim_rect.x0 + (available_width - page_width) / 2;
	pos->content_translate_y = 
		media_rect.y0 - trim_rect.y0 + (available_height - page_height) / 2;

	
	/* if needed, clip the contents to the bleed-box */
	if(adjust_bleed_clipping(ctx, doc, page, pos) < 0)
		return(-2);

	return(0);
}

int
pdf_annot_ink_list_count(fz_context *ctx, pdf_annot *annot)
{
	pdf_obj *ink_list;
	check_allowed_subtypes(ctx, annot, PDF_NAME_InkList, ink_list_subtypes);
	ink_list = pdf_dict_get(ctx, annot->obj, PDF_NAME_InkList);
	return pdf_array_len(ctx, ink_list);
}

int
pdf_annot_quad_point_count(fz_context *ctx, pdf_annot *annot)
{
	pdf_obj *quad_points;
	check_allowed_subtypes(ctx, annot, PDF_NAME_QuadPoints, quad_point_subtypes);
	quad_points = pdf_dict_get(ctx, annot->obj, PDF_NAME_QuadPoints);
	return pdf_array_len(ctx, quad_points);
}

int
pdf_annot_vertex_count(fz_context *ctx, pdf_annot *annot)
{
	pdf_obj *vertices;
	check_allowed_subtypes(ctx, annot, PDF_NAME_Vertices, vertices_subtypes);
	vertices = pdf_dict_get(ctx, annot->obj, PDF_NAME_Vertices);
	return pdf_array_len(ctx, vertices) / 2;
}

int
pdf_annot_ink_list_stroke_count(fz_context *ctx, pdf_annot *annot, int i)
{
	pdf_obj *ink_list;
	pdf_obj *stroke;
	check_allowed_subtypes(ctx, annot, PDF_NAME(InkList), ink_list_subtypes);
	ink_list = pdf_dict_get(ctx, annot->obj, PDF_NAME(InkList));
	stroke = pdf_array_get(ctx, ink_list, i);
	return pdf_array_len(ctx, stroke) / 2;
}

pdf_obj *
pdf_copy_array(fz_context *ctx, pdf_obj *obj)
{
	pdf_obj *arr;
	int i;
	int n;

	RESOLVE(obj);
	if (!obj)
		return NULL; /* Can't warn :( */
	if (obj->kind != PDF_ARRAY)
		fz_warn(ctx, "assert: not an array (%s)", pdf_objkindstr(obj));

	arr = pdf_new_array(ctx, pdf_array_len(obj));
	n = pdf_array_len(obj);
	for (i = 0; i < n; i++)
		pdf_array_push(arr, pdf_array_get(obj, i));

	return arr;
}