/* Copyright (C) 2001-2020 Artifex Software, Inc.

   All Rights Reserved.

   This software is provided AS-IS with no warranty, either express or

   implied.

   This software is distributed under license and may not be copied,

   modified or distributed except as expressly authorized under the terms

   of the license contained in the file LICENSE in this distribution.

   Refer to licensing information at http://www.artifex.com or contact

   Artifex Software, Inc.,  1305 Grant Avenue - Suite 200, Novato,

   CA 94945, U.S.A., +1(415)492-9861, for further information.

*/

/*$Id: gdevtxtw.c 7795 2007-03-23 13:56:11Z tim $ */

/* Device for Unicode (UTF-8 or UCS2) text extraction */

#include "memory_.h"

#include "string_.h"

#include "gp.h"     /* for gp_file_name_sizeof */

#include "gx.h"

#include "gserrors.h"

#include "gsparam.h"

#include "gsutil.h"

#include "gxdevice.h"

#include "gsdevice.h"   /* requires gsmatrix.h */

#include "gxfont.h"

#include "gxfont0.h"

#include "gstext.h"

#include "gxfcid.h"

#include "gxgstate.h"

#include "gxpath.h"

#include "gdevagl.h"

#include "gxdevsop.h"

#include "gzpath.h"

#include "gdevkrnlsclass.h" /* 'standard' built in subclasses, currently First/Last Page and obejct filter */

#include "gxchar.h"

/* #define TRACE_TXTWRITE 1 */

extern single_glyph_list_t SingleGlyphList[];

extern double_glyph_list_t DoubleGlyphList[];

extern treble_glyph_list_t TrebleGlyphList[];

extern quad_glyph_list_t QuadGlyphList[];

/*

 * Define the structure used to return glyph width information.  Note that

 * there are two different sets of width information: real-number (x,y)

 * values, which give the true advance width, and an integer value, which

 * gives an X advance width for WMode = 0 or a Y advance width for WMode = 1.

 * The return value from txt_glyph_width() indicates which of these is/are

 * valid.

 */

typedef struct txt_glyph_width_s {

    double w;

    gs_point xy;

    gs_point v;       /* glyph origin shift */

} txt_glyph_width_t;

typedef struct txt_glyph_widths_s {

    txt_glyph_width_t Width;    /* unmodified, for Widths */

    txt_glyph_width_t real_width; /* possibly modified, for rendering */

    bool replaced_v;

} txt_glyph_widths_t;

/* Structure to record the Unicode characters, the total width of the text

 * recorded, and various useful attributes such as the font, size, colour

 * rendering mode, writing mode etc. These are stored as a series of x-ordered

 * entries in a list, using the starting x co-ordinate.

 */

typedef struct text_list_entry_s {

    struct text_list_entry_s *previous;

    struct text_list_entry_s *next;

    gs_point start;

    gs_point end;

    gs_point FontBBox_bottomleft, FontBBox_topright;

    float *Widths;

    float *Advs;

    unsigned short *Unicode_Text;

    int Unicode_Text_Size;

    int render_mode;

    gs_matrix matrix;   /* Tm et al */

    gs_font *font;

    char *FontName;

    int wmode;      /* WMode of font */

    double PaintType0Width;

    double size;

} text_list_entry_t;

/* Structure to maintain a list of text fragments, ordered by X co-ordinate.

 * These structures are themselves maintained in a Y-ordered list.

 */

typedef struct page_text_list_s {

    struct page_text_list_s *previous;

    struct page_text_list_s *next;

    gs_point start;

    float MinY, MaxY;

    text_list_entry_t *x_ordered_list;

} page_text_list_t;

/* A simple structure to maintain the lists of text fragments, it is also

 * a convenient place to record the page number and anything else we may

 * want to record that is relevant to the page rather than the text.

 */

typedef struct page_text_s {

    int PageNum;

    page_text_list_t *y_ordered_list;

    text_list_entry_t *unsorted_text_list;

} page_text_t;

/* The custom sub-classed device structure */

typedef struct gx_device_txtwrite_s {

    gx_device_common;

    page_text_t PageData;

    char fname[gp_file_name_sizeof];  /* OutputFile */

    gp_file *file;

    int TextFormat;

#ifdef TRACE_TXTWRITE

    gp_file *DebugFile;

#endif

} gx_device_txtwrite_t;

/* Device procedures */

static dev_proc_open_device(txtwrite_open_device);

static dev_proc_close_device(txtwrite_close_device);

static dev_proc_output_page(txtwrite_output_page);

static dev_proc_fill_rectangle(txtwrite_fill_rectangle);

static dev_proc_get_params(txtwrite_get_params);

static dev_proc_put_params(txtwrite_put_params);

static dev_proc_fill_path(txtwrite_fill_path);

static dev_proc_stroke_path(txtwrite_stroke_path);

static dev_proc_text_begin(txtwrite_text_begin);

static dev_proc_strip_copy_rop(txtwrite_strip_copy_rop);

static dev_proc_dev_spec_op(txtwrite_dev_spec_op);

/* The device prototype */

#define X_DPI 72

#define Y_DPI 72

/* Define the text enumerator. */

typedef struct textw_text_enum_s {

    gs_text_enum_common;

    gs_text_enum_t *pte_fallback;

    double d1_width;

    bool d1_width_set;

    bool charproc_accum;

    bool cdevproc_callout;

    double cdevproc_result[10];

    float *Widths;

    float *Advs;

    unsigned short *TextBuffer;

    int TextBufferIndex;

    text_list_entry_t *text_state;

} textw_text_enum_t;

#define private_st_textw_text_enum()\

  extern_st(st_gs_text_enum);\

  gs_private_st_suffix_add0(st_textw_text_enum, textw_text_enum_t,\

    "textw_text_enum_t", textw_text_enum_enum_ptrs, textw_text_enum_reloc_ptrs,\

    st_gs_text_enum)

private_st_textw_text_enum();

const gx_device_txtwrite_t gs_txtwrite_device =

{

    /* Define the device as 8-bit gray scale to avoid computing halftones. */

    std_device_dci_body(gx_device_txtwrite_t, 0, "txtwrite",

                        DEFAULT_WIDTH_10THS * X_DPI / 10,

                        DEFAULT_HEIGHT_10THS * Y_DPI / 10,

                        X_DPI, Y_DPI,

                        1, 8, 255, 0, 256, 1),

    {txtwrite_open_device,

     NULL, /*gx_upright_get_initial_matrix,*/

     NULL, /*gx_default_sync_output,*/

     txtwrite_output_page,

     txtwrite_close_device,

     NULL, /*gx_default_gray_map_rgb_color,*/

     NULL, /*gx_default_gray_map_color_rgb,*/

     txtwrite_fill_rectangle,               /* Can't be NULL and there is no gx_default_fill_rectangle! */

     NULL, /*gx_default_tile_rectangle,*/

     NULL, /*gx_default_copy_mono,*/

     NULL, /*gx_default_copy_color,*/

     NULL, /*gx_default_draw_line,*/

     NULL, /*gx_default_get_bits,*/

     txtwrite_get_params,

     txtwrite_put_params,

     NULL, /*gx_default_map_cmyk_color,*/

     NULL, /*gx_default_get_xfont_procs,*/

     NULL, /*gx_default_get_xfont_device,*/

     NULL, /*gx_default_map_rgb_alpha_color,*/

     gx_page_device_get_page_device, /*gx_page_device_get_page_device,*/

     NULL,      /* get_alpha_bits */

     NULL, /*gx_default_copy_alpha,*/

     NULL,      /* get_band */

     NULL,      /* copy_rop */

     txtwrite_fill_path,

     txtwrite_stroke_path,

     NULL, /*gx_default_fill_mask,*/

     NULL, /*gx_default_fill_trapezoid,*/

     NULL, /*gx_default_fill_parallelogram,*/

     NULL, /*gx_default_fill_triangle,*/

     NULL, /*gx_default_draw_thin_line,*/

     NULL,                      /* begin image */

     NULL,      /* image_data */

     NULL,      /* end_image */

     NULL, /*gx_default_strip_tile_rectangle,*/

     txtwrite_strip_copy_rop,

     NULL,      /* get_clipping_box */

     NULL, /* txtwrite_begin_typed_image */

     NULL,      /* get_bits_rectangle */

     NULL, /*gx_default_map_color_rgb_alpha,*/

     gx_null_create_compositor,

     NULL,      /* get_hardware_params */

     txtwrite_text_begin,

     NULL,      /* finish_copydevice */

     NULL,      /* begin_transparency_group */

     NULL,      /* end_transparency_group */

     NULL,      /* begin_transparency_mask */

     NULL,      /* end_transparency_mask */

     NULL,      /* discard_transparency_layer */

     NULL,      /* get_color_mapping_procs */

     NULL,      /* get_color_comp_index */

     NULL,      /* encode_color */

     NULL,      /* decode_color */

     NULL,                      /* pattern manager */

     NULL,                      /* fill_rectangle_hl_color */

     NULL,                      /* include_color_space */

     NULL,                      /* fill_linear_color_scanline */

     NULL,                      /* fill_linear_color_trapezoid */

     NULL,                      /* fill_linear_color_triangle */

     NULL,                      /* update_spot_equivalent_colors */

     NULL,                      /* ret_devn_params */

     NULL,                      /* fillpage */

     NULL,                      /* push_transparency_state */

     NULL,                      /* pop_transparency_state */

     NULL,                      /* put_image */

     txtwrite_dev_spec_op,      /* dev_spec_op */

     NULL,                      /* copy_planes */

     NULL,                      /* get_profile */

     NULL,                      /* set_graphics_type_tag */

     NULL,                      /* strip_copy_rop2 */

     NULL                       /* strip_tile_rect_devn */

    },

    { 0 },      /* Page Data */

    { 0 },      /* Output Filename */

    0,        /* Output FILE * */

    3       /* TextFormat */

};

typedef struct gx_device_textwrite_s gx_device_textw;

static const gs_param_item_t txt_param_items[] = {

#define pi(key, type, memb) { key, type, offset_of(gx_device_txtwrite_t, memb) }

    pi("TextFormat", gs_param_type_int, TextFormat),

#undef pi

    gs_param_item_end

};

/* ---------------- Open/close/page ---------------- */

static int

txtwrite_open_device(gx_device * dev)

{

    gx_device_txtwrite_t *const tdev = (gx_device_txtwrite_t *) dev;

    int code = 0;

    gx_device_fill_in_procs(dev);

    if (tdev->fname[0] == 0)

        return_error(gs_error_undefinedfilename);

    tdev->PageData.PageNum = 0;

    tdev->PageData.y_ordered_list = NULL;

    tdev->file = NULL;

#ifdef TRACE_TXTWRITE

    tdev->DebugFile = gp_fopen(dev->memory,"/temp/txtw_dbg.txt", "wb+");

#endif

    dev->color_info.separable_and_linear = GX_CINFO_SEP_LIN;

    set_linear_color_bits_mask_shift(dev);

    dev->interpolate_control = 0;

    code = install_internal_subclass_devices((gx_device **)&dev, NULL);

    return code;

}

static int

txtwrite_close_device(gx_device * dev)

{

    int code = 0;

    gx_device_txtwrite_t *const tdev = (gx_device_txtwrite_t *) dev;

    if (tdev->file) {

        code = gx_device_close_output_file(dev, tdev->fname, tdev->file);

        tdev->file = 0;

    }

#ifdef TRACE_TXTWRITE

    gp_fclose(tdev->DebugFile);

#endif

    return code;

}

/* Routine inspects horizontal lines of text to see if they can be collapsed

 * into a single line. This essentially detects superscripts and subscripts

 * as well as lines which are slightly mis-aligned.

 */

static int merge_vertically(gx_device_txtwrite_t *tdev)

{

#ifdef TRACE_TXTWRITE

    text_list_entry_t *debug_x;

#endif

    page_text_list_t *y_list = tdev->PageData.y_ordered_list;

    while (y_list && y_list->next) {

        page_text_list_t *next = y_list->next;

        bool collision = false;

        float overlap = (y_list->start.y + y_list->MaxY) - (next->start.y + next->MinY);

        if (overlap >= (y_list->MaxY - y_list->MinY) / 4) {

            /* At least a 25% overlap, lets test for x collisions */

            text_list_entry_t *upper = y_list->x_ordered_list, *lower;

            while (upper && !collision) {

                lower = next->x_ordered_list;

                while (lower && !collision) {

                    if (upper->start.x >= lower->start.x) {

                        if (upper->start.x <= lower->end.x) {

                            /* Collision */

                            collision = true;

                            break;

                        }

                    } else {

                        if (upper->end.x > lower->start.x) {

                            /* Collision */

                            collision = true;

                            break;

                        }

                    }

                    lower = lower->next;

                }

                upper = upper->next;

            }

            if (!collision) {

                text_list_entry_t *from, *to, *new_order, *current;

                /* Consolidate y lists */

                to = y_list->x_ordered_list;

                from = next->x_ordered_list;

#ifdef TRACE_TXTWRITE

                gp_fprintf(tdev->DebugFile, "\nConsolidating two horizontal lines, line 1:");

                debug_x = from;

                while (debug_x) {

                    gp_fprintf(tdev->DebugFile, "\n\t");

                    gp_fwrite(debug_x->Unicode_Text, sizeof(unsigned short), debug_x->Unicode_Text_Size, tdev->DebugFile);

                    debug_x = debug_x->next;

                }

                gp_fprintf(tdev->DebugFile, "\nConsolidating two horizontal lines, line 2");

                debug_x = to;

                while (debug_x) {

                    gp_fprintf(tdev->DebugFile, "\n\t");

                    gp_fwrite(debug_x->Unicode_Text, sizeof(unsigned short), debug_x->Unicode_Text_Size, tdev->DebugFile);

                    debug_x = debug_x->next;

                }

#endif

                if (from->start.x < to->start.x) {

                    current = new_order = from;

                    from = from->next;

                } else {

                    current = new_order = to;

                    to = to->next;

                }

                while (to && from) {

                    if (to->start.x < from->start.x) {

                        current->next = to;

                        to->previous = current;

                        to = to->next;

                    } else {

                        current->next = from;

                        from->previous = current;

                        from = from->next;

                    }

                    current = current->next;

                }

                if (to) {

                    to->previous = current;

                    current->next = to;

                } else {

                    if (from) {

                        from->previous = current;

                        current->next = from;

                    }

                }

                y_list->x_ordered_list = new_order;

#ifdef TRACE_TXTWRITE

                gp_fprintf(tdev->DebugFile, "\nAfter:");

                debug_x = new_order;

                while (debug_x) {

                    gp_fprintf(tdev->DebugFile, "\n\t");

                    gp_fwrite(debug_x->Unicode_Text, sizeof(unsigned short), debug_x->Unicode_Text_Size, tdev->DebugFile);

                    debug_x = debug_x->next;

                }

                gp_fprintf(tdev->DebugFile, "\n");

#endif

                y_list->next = next->next;

                if (next->next)

                    next->next->previous = y_list;

                gs_free(tdev->memory, next, 1, sizeof(page_text_list_entry_t), "txtwrite free text list");

            } else

                y_list = next;

        } else

            y_list = next;

    }

    return 0;

}

/* Routine to merge horizontally adjacent text fragments. If the distance

 * between two horizontal fragments is small, then they are treated as one

 * frament of text, if its larger then we insert a space (and set the Width

 * entry appropriately). Otherwise we leave them as separate.

 */

static int merge_horizontally(gx_device_txtwrite_t *tdev)

{

#ifdef TRACE_TXTWRITE

    text_list_entry_t *debug_x;

#endif

    unsigned short UnicodeSpace = 0x20;

    page_text_list_t *y_list = tdev->PageData.y_ordered_list;

    while (y_list) {

        float average_width;

        text_list_entry_t *from, *to;

        from = y_list->x_ordered_list;

        to = from->next;

        while (from && to) {

            average_width = (from->end.x - from->start.x) / from->Unicode_Text_Size;

            if (to->start.x - from->end.x < average_width / 2) {

                /* consolidate fragments */

                unsigned short *NewText;

                float *NewWidths;

                NewText = (unsigned short *)gs_malloc(tdev->memory->stable_memory,

                    (from->Unicode_Text_Size + to->Unicode_Text_Size), sizeof(unsigned short), "txtwrite alloc working text buffer");

                NewWidths = (float *)gs_malloc(tdev->memory->stable_memory,

                    (from->Unicode_Text_Size + to->Unicode_Text_Size), sizeof(float), "txtwrite alloc Widths array");

                if (!NewText || !NewWidths) {

                    if (NewText)

                        gs_free(tdev->memory, NewText, from->Unicode_Text_Size + to->Unicode_Text_Size, sizeof (unsigned short), "free working text fragment");

                    /* ran out of memory, don't consolidate */

                    from = from->next;

                    to = to->next;

                } else {

#ifdef TRACE_TXTWRITE

                    gp_fprintf(tdev->DebugFile, "Consolidating two horizontal fragments in one line, before:\n\t");

                    gp_fwrite(from->Unicode_Text, sizeof(unsigned short), from->Unicode_Text_Size, tdev->DebugFile);

                    gp_fprintf(tdev->DebugFile, "\n\t");

                    gp_fwrite(to->Unicode_Text, sizeof(unsigned short), to->Unicode_Text_Size, tdev->DebugFile);

#endif

                    memcpy(NewText, from->Unicode_Text, from->Unicode_Text_Size * sizeof(unsigned short));

                    memcpy(&NewText[from->Unicode_Text_Size], to->Unicode_Text, to->Unicode_Text_Size * sizeof(unsigned short));

                    memcpy(NewWidths, from->Widths, from->Unicode_Text_Size * sizeof(float));

                    memcpy(&NewWidths[from->Unicode_Text_Size], to->Widths, to->Unicode_Text_Size * sizeof(float));

                    gs_free(tdev->memory, from->Unicode_Text, from->Unicode_Text_Size, sizeof (unsigned short), "free consolidated text fragment");

                    gs_free(tdev->memory, to->Unicode_Text, to->Unicode_Text_Size, sizeof (unsigned short), "free consolidated text fragment");

                    gs_free(tdev->memory, from->Widths, from->Unicode_Text_Size, sizeof (float), "free consolidated Widths array");

                    gs_free(tdev->memory, to->Widths, to->Unicode_Text_Size, sizeof (float), "free consolidated Widths array");

                    gs_free(tdev->memory, to->FontName, 1, strlen(from->FontName) + 1, "free FontName");

                    from->Unicode_Text = NewText;

                    from->Unicode_Text_Size += to->Unicode_Text_Size;

                    from->Widths = NewWidths;

#ifdef TRACE_TXTWRITE

                    gp_fprintf(tdev->DebugFile, "After:\n\t");

                    gp_fwrite(from->Unicode_Text, sizeof(unsigned short), from->Unicode_Text_Size, tdev->DebugFile);

#endif

                    from->end = to->end;

                    from->next = to->next;

                    if (from->next)

                        from->next->previous = from;

                    gs_free(tdev->memory, to, 1, sizeof(text_list_entry_t), "free consolidated fragment");

                    to = from->next;

                }

            } else {

                if (to->start.x - from->end.x < average_width *2){

                    unsigned short *NewText;

                    float *NewWidths;

                    NewText = (unsigned short *)gs_malloc(tdev->memory->stable_memory,

                        (from->Unicode_Text_Size + to->Unicode_Text_Size + 1), sizeof(unsigned short), "txtwrite alloc text state");

                    NewWidths = (float *)gs_malloc(tdev->memory->stable_memory,

                        (from->Unicode_Text_Size + to->Unicode_Text_Size + 1), sizeof(float), "txtwrite alloc Widths array");

                    if (!NewText || !NewWidths) {

                        if (NewText)

                            gs_free(tdev->memory, NewText, from->Unicode_Text_Size + to->Unicode_Text_Size, sizeof (unsigned short), "free working text fragment");

                        /* ran out of memory, don't consolidate */

                        from = from->next;

                        to = to->next;

                    } else {

                        memcpy(NewText, from->Unicode_Text, from->Unicode_Text_Size * sizeof(unsigned short));

                        memcpy(&NewText[from->Unicode_Text_Size], &UnicodeSpace, sizeof(unsigned short));

                        memcpy(&NewText[from->Unicode_Text_Size + 1], to->Unicode_Text, to->Unicode_Text_Size * sizeof(unsigned short));

                        memcpy(NewWidths, from->Widths, from->Unicode_Text_Size * sizeof(float));

                        NewWidths[from->Unicode_Text_Size] = to->start.x - from->end.x;

                        memcpy(&NewWidths[from->Unicode_Text_Size + 1], to->Widths, to->Unicode_Text_Size * sizeof(float));

                        gs_free(tdev->memory, from->Unicode_Text, from->Unicode_Text_Size, sizeof (unsigned short), "free consolidated text fragment");

                        gs_free(tdev->memory, to->Unicode_Text, to->Unicode_Text_Size, sizeof (unsigned short), "free consolidated text fragment");

                        gs_free(tdev->memory, from->Widths, from->Unicode_Text_Size, sizeof (float), "free consolidated Widths array");

                        gs_free(tdev->memory, to->Widths, to->Unicode_Text_Size, sizeof (float), "free consolidated Widths array");

                        gs_free(tdev->memory, to->FontName, 1, strlen(from->FontName) + 1, "free FontName");

                        from->Unicode_Text = NewText;

                        from->Unicode_Text_Size += to->Unicode_Text_Size + 1;

                        from->Widths = NewWidths;

                        from->end = to->end;

                        from->next = to->next;

                        if (from->next)

                            from->next->previous = from;

                        gs_free(tdev->memory, to, 1, sizeof(text_list_entry_t), "free consolidated fragment");

                        to = from->next;

                    }

                } else {

                    from = from->next;

                    to = to->next;

                }

            }

        }

        y_list = y_list->next;

    }

    return 0;

}

static int write_simple_text(unsigned short *text, int count, gx_device_txtwrite_t *tdev)

{

    switch(tdev->TextFormat) {

        case 2:

            gp_fwrite(text, sizeof (unsigned short), count, tdev->file);

            break;

        case 3:

            {

                int i;

                unsigned short *UTF16 = (unsigned short *)text;

                unsigned char UTF8[3];

                for (i=0;i<count;i++) {

                    if (*UTF16 < 0x80) {

                        UTF8[0] = *UTF16 & 0xff;

                        gp_fwrite (UTF8, sizeof(unsigned char), 1, tdev->file);

                    } else {

                        if (*UTF16 < 0x800) {

                            UTF8[0] = (*UTF16 >> 6) + 0xC0;

                            UTF8[1] = (*UTF16 & 0x3F) + 0x80;

                            gp_fwrite (UTF8, sizeof(unsigned char), 2, tdev->file);

                        } else {

                            UTF8[0] = (*UTF16 >> 12) + 0xE0;

                            UTF8[1] = ((*UTF16 >> 6) & 0x3F) + 0x80;

                            UTF8[2] = (*UTF16 & 0x3F) + 0x80;

                            gp_fwrite (UTF8, sizeof(unsigned char), 3, tdev->file);

                        }

                    }

                    UTF16++;

                }

            }

            break;

        default:

            return gs_note_error(gs_error_rangecheck);

            break;

    }

    return 0;

}

static int simple_text_output(gx_device_txtwrite_t *tdev)

{

    int chars_wide;

    float char_size, min_size, min_width_size;

#ifdef TRACE_TXTWRITE

    text_list_entry_t *debug_x;

#endif

    text_list_entry_t * x_entry;

    page_text_list_t *y_list;

    unsigned short UnicodeSpace = 0x20, UnicodeEOL[2] = {0x00D, 0x0a};

    merge_vertically(tdev);

    merge_horizontally(tdev);

    min_size = (float)tdev->width;

    /* Estimate maximum text density */

    y_list = tdev->PageData.y_ordered_list;

    while (y_list) {

        x_entry = y_list->x_ordered_list;

        while (x_entry) {

            if (x_entry->size < min_size)

                min_size = x_entry->size;

            x_entry = x_entry->next;

        }

        y_list = y_list->next;

    }

    min_width_size = min_size;

    y_list = tdev->PageData.y_ordered_list;

    while (y_list) {

        float width;

        x_entry = y_list->x_ordered_list;

        while (x_entry) {

            width = (x_entry->end.x - x_entry->start.x) / x_entry->Unicode_Text_Size;

            if (x_entry->next) {

                /* If we have following text, check to see if *not* using the newly calculated size would result in

                 * the end of the text going past the beginning of the following text. If it does then we must

                 * use the new minimum, regardless of how small it is! The foregoing comment isn't quite true...

                 * we never used a width of 0 because that would result in an endless loop, we need to allow a little

                 * slop in case rounding errors mean that the x difference from start to end of the text is almost,

                 * but not quite, zero.

                 */

                if (x_entry->start.x + ((x_entry->Unicode_Text_Size + 1) * min_width_size) > x_entry->next->start.x && width > 0.001)

                    min_width_size = width;

            } else {

                if (width < min_width_size && width >= (float)min_size * 0.75)

                    min_width_size = width;

            }

            x_entry = x_entry->next;

        }

        y_list = y_list->next;

    }

    min_size = min_width_size;

    chars_wide = (int)ceil(tdev->width / min_size);

    char_size = (float)tdev->width / (float)chars_wide;

    y_list = tdev->PageData.y_ordered_list;

    while (y_list) {

        float xpos = 0;

        x_entry = y_list->x_ordered_list;

        while (x_entry) {

            while (xpos < x_entry->start.x) {

                write_simple_text(&UnicodeSpace, 1, tdev);

                xpos += char_size;

            }

            write_simple_text(x_entry->Unicode_Text, x_entry->Unicode_Text_Size, tdev);

            xpos += x_entry->Unicode_Text_Size * char_size;

            if (x_entry->next) {

                x_entry = x_entry->next;

            } else {

                x_entry = NULL;

            }

        }

        write_simple_text((unsigned short *)&UnicodeEOL, 2, tdev);

        if (y_list->next) {

            y_list = y_list->next;

        } else {

            y_list = NULL;

        }

    }

    return 0;

}

static int escaped_Unicode (unsigned short Unicode, char *Buf)

{

    switch (Unicode)

    {

    case 0x3C: gs_sprintf(Buf, "<"); break;

    case 0x3E: gs_sprintf(Buf, ">"); break;

    case 0x26: gs_sprintf(Buf, "&"); break;

    case 0x22: gs_sprintf(Buf, """); break;

    case 0x27: gs_sprintf(Buf, "'"); break;

    default:

        if (Unicode >= 32 && Unicode <= 127)

            gs_sprintf(Buf, "%c", Unicode);

        else

            gs_sprintf(Buf, "&#x%x;", Unicode);

        break;

    }

    return 0;

}

static int decorated_text_output(gx_device_txtwrite_t *tdev)

{

    int i;

    text_list_entry_t * x_entry, *next_x;

    char TextBuffer[512], Escaped[32];

    float xpos;

    page_text_list_t *y_list;

#ifdef TRACE_TXTWRITE

    text_list_entry_t *debug_x;

#endif

    if (tdev->TextFormat == 0) {

        gp_fwrite("<page>\n", sizeof(unsigned char), 7, tdev->file);

        x_entry = tdev->PageData.unsorted_text_list;

        while (x_entry) {

            next_x = x_entry->next;

            gs_sprintf(TextBuffer, "<span bbox=\"%0.0f %0.0f %0.0f %0.0f\" font=\"%s\" size=\"%0.4f\">\n", x_entry->start.x, x_entry->start.y,

                x_entry->end.x, x_entry->end.y, x_entry->FontName,x_entry->size);

            gp_fwrite(TextBuffer, 1, strlen(TextBuffer), tdev->file);

            xpos = x_entry->start.x;

            for (i=0;i<x_entry->Unicode_Text_Size;i++) {

                escaped_Unicode(x_entry->Unicode_Text[i], (char *)&Escaped);

                gs_sprintf(TextBuffer, "<char bbox=\"%0.0f %0.0f %0.0f %0.0f\" c=\"%s\"/>\n", xpos,

                    x_entry->start.y, xpos + x_entry->Widths[i], x_entry->end.y, Escaped);

                gp_fwrite(TextBuffer, 1, strlen(TextBuffer), tdev->file);

                xpos += x_entry->Widths[i];

            }

            gp_fwrite("</span>\n", sizeof(unsigned char), 8, tdev->file);

            x_entry = next_x;

        }

        gp_fwrite("</page>\n", sizeof(unsigned char), 8, tdev->file);

    } else {

        merge_vertically(tdev);

        merge_horizontally(tdev);

        y_list = tdev->PageData.y_ordered_list;

        gp_fwrite("<page>\n", sizeof(unsigned char), 7, tdev->file);

        /* Walk the list looking for 'blocks' */

        do {

            page_text_list_t *temp;

            page_text_t block;

            page_text_list_t *block_line;

            float BBox[4];

            memset(&block, 0x00, sizeof(page_text_t));

            memset(BBox, 0x00, sizeof(float) * 4);

            while (y_list) {

                if (block.y_ordered_list) {

                    text_list_entry_t *x_entry = y_list->x_ordered_list;

                    block_line = block.y_ordered_list;

                    while (x_entry) {

                        if (x_entry->start.x > BBox[2] || x_entry->end.x < BBox[0] ||

                            x_entry->start.y > (BBox[1] + (BBox[3] - BBox[1]))) {

                                ;

                        } else {

                            block_line->next = (page_text_list_t *)gs_malloc(tdev->memory->stable_memory, 1,

                                sizeof(page_text_list_t), "txtwrite alloc Y-list");

                            memset(block_line->next, 0x00, sizeof(page_text_list_t));

                            block_line = block_line->next;

                            block_line->x_ordered_list = x_entry;

                            if(x_entry->next)

                                x_entry->next->previous = x_entry->previous;

                            if (x_entry->previous)

                                x_entry->previous->next = x_entry->next;

                            else {

                                if (x_entry->next == 0x00) {

                                    /* remove Y entry */

                                    temp = y_list->next;

                                    if (y_list->previous)

                                        y_list->previous->next = y_list->next;

                                    if (y_list->next)

                                        y_list->next->previous = y_list->previous;

                                    else {

                                        if (y_list->previous == 0x00) {

                                            tdev->PageData.y_ordered_list = 0x00;

                                        }

                                    }

                                    gs_free(tdev->memory, y_list, 1, sizeof(page_text_list_t), "txtwrite free text list");

                                    if (tdev->PageData.y_ordered_list == y_list)

                                        tdev->PageData.y_ordered_list = temp;

                                    y_list = temp;

                                    x_entry = x_entry->next;

                                    continue;

                                }

                            }

                            if (block_line->x_ordered_list->start.x < BBox[0])

                                BBox[0] = block_line->x_ordered_list->start.x;

                            if (block_line->x_ordered_list->start.y < BBox[1])

                                BBox[1] = block_line->x_ordered_list->start.y;

                            if (block_line->x_ordered_list->end.x < BBox[2])

                                BBox[2] = block_line->x_ordered_list->end.x;

                            if (block_line->x_ordered_list->end.y + block_line->x_ordered_list->FontBBox_topright.y < BBox[3])

                                BBox[3] = block_line->x_ordered_list->end.y + block_line->x_ordered_list->FontBBox_topright.y;

                        }

                        x_entry = x_entry->next;

                    }

                } else {

                    block.y_ordered_list = block_line = (page_text_list_t *)gs_malloc(tdev->memory->stable_memory, 1,

                        sizeof(page_text_list_t), "txtwrite alloc Y-list");

                    memset(block_line, 0x00, sizeof(page_text_list_t));

                    block_line->x_ordered_list = y_list->x_ordered_list;

                    y_list->x_ordered_list = y_list->x_ordered_list->next;

                    if (y_list->x_ordered_list == 0x00) {

                        temp = y_list->next;

                        if (y_list->previous)

                            y_list->previous->next = y_list->next;

                        if (y_list->next)

                            y_list->next->previous = y_list->previous;

                        else {

                            if (y_list->previous == 0x00) {

                                tdev->PageData.y_ordered_list = 0x00;

                            }

                        }

                        gs_free(tdev->memory, y_list, 1, sizeof(page_text_list_t), "txtwrite free text list");

                        if (tdev->PageData.y_ordered_list == y_list)

                            tdev->PageData.y_ordered_list = temp;

                        y_list = temp;

                        continue;

                    }

                    block_line->x_ordered_list->next = block_line->x_ordered_list->previous = 0x00;

                    BBox[0] = block_line->x_ordered_list->start.x;

                    BBox[1] = block_line->x_ordered_list->start.y;

                    BBox[2] = block_line->x_ordered_list->end.x;

                    BBox[3] = block_line->x_ordered_list->end.y + block_line->x_ordered_list->FontBBox_topright.y;

                }

                if (y_list)

                    y_list = y_list->next;

            }

            /* FIXME - need to free the used memory in here */

            gp_fwrite("<block>\n", sizeof(unsigned char), 8, tdev->file);

            block_line = block.y_ordered_list;

            while (block_line) {

                gp_fwrite("<line>\n", sizeof(unsigned char), 7, tdev->file);

                x_entry = block_line->x_ordered_list;

                while(x_entry) {

                    gs_sprintf(TextBuffer, "<span bbox=\"%0.0f %0.0f %0.0f %0.0f\" font=\"%s\" size=\"%0.4f\">\n", x_entry->start.x, x_entry->start.y,

                        x_entry->end.x, x_entry->end.y, x_entry->FontName,x_entry->size);

                    gp_fwrite(TextBuffer, 1, strlen(TextBuffer), tdev->file);

                    xpos = x_entry->start.x;

                    for (i=0;i<x_entry->Unicode_Text_Size;i++) {

                        escaped_Unicode(x_entry->Unicode_Text[i], (char *)&Escaped);

                        gs_sprintf(TextBuffer, "<char bbox=\"%0.0f %0.0f %0.0f %0.0f\" c=\"%s\"/>\n", xpos,

                            x_entry->start.y, xpos + x_entry->Widths[i], x_entry->end.y, Escaped);

                        gp_fwrite(TextBuffer, 1, strlen(TextBuffer), tdev->file);

                        xpos += x_entry->Widths[i];

                    }

                    gp_fwrite("</span>\n", sizeof(unsigned char), 8, tdev->file);

                    x_entry = x_entry->next;

                }

                gp_fwrite("</line>\n", sizeof(unsigned char), 8, tdev->file);

                block_line = block_line->next;

            }

            gp_fwrite("</block>\n", sizeof(unsigned char), 9, tdev->file);

            y_list = tdev->PageData.y_ordered_list;

        } while (y_list);

        gp_fwrite("</page>\n", sizeof(unsigned char), 8, tdev->file);

    }

    return 0;

}

static int extract_text_output(gx_device_txtwrite_t *tdev)

{

    text_list_entry_t* entry;

    gp_fprintf(tdev->file, "<page>\n");

    for (entry = tdev->PageData.unsorted_text_list;

            entry;

            entry = entry->next

            ) {

        float x = entry->start.x;

        int i;

        gp_fprintf(tdev->file,

                "<span bbox=\"%0.4f %0.4f %0.4f %0.4f\" font=\"%s\" size=\"%0.4f\">\n",

                entry->start.x,

                entry->start.y,

                entry->end.x,

                entry->end.y,

                entry->FontName,

                entry->size

                );

        for (i=0; i<entry->Unicode_Text_Size; i++) {

            float x_next = x + entry->Widths[i];

            char escaped[32];

            escaped_Unicode(entry->Unicode_Text[i], escaped);

            gp_fprintf(tdev->file,

                    "<char bbox=\"%0.4f %0.4f %0.4f %0.4f\" c=\"%s\" adv=\"%0.4f\"/>\n",

                    x,

                    entry->start.y,

                    x_next,

                    entry->end.y,

                    escaped,

                    entry->Advs[i]

                    );

            x = x_next;

        }

        gp_fprintf(tdev->file, "</span>\n");

    }

    gp_fprintf(tdev->file, "</page>\n");

    return 0;

}

static int

txtwrite_output_page(gx_device * dev, int num_copies, int flush)

{

    int code;

    gx_device_txtwrite_t *const tdev = (gx_device_txtwrite_t *) dev;

    text_list_entry_t * x_entry, *next_x;

    page_text_list_t *y_list;

    gs_parsed_file_name_t parsed;

    const char *fmt;

    const short BOM = 0xFEFF;

    if (!tdev->file) {

        /* Either this is the first page, or we're doing one file per page */

        code = gx_device_open_output_file(dev, tdev->fname,

                true, false, &tdev->file); /* binary, sequential */

        if (code < 0)

            return code;

    }

    switch(tdev->TextFormat) {

        case 0:

        case 1:

            code = decorated_text_output(tdev);

            if (code < 0)

                return code;

            break;

        case 2:

            gp_fwrite (&BOM, sizeof(unsigned short), 1, tdev->file);

            /* fall through */

        case 3:

            code = simple_text_output(tdev);

            if (code < 0)

                return code;

            break;

        case 4:

            code = extract_text_output(tdev);

            if (code < 0)

                return code;

            break;

        default:

            return gs_note_error(gs_error_rangecheck);

            break;