/*====================================================================*

 -  Copyright (C) 2001 Leptonica.  All rights reserved.

 -

 -  Redistribution and use in source and binary forms, with or without

 -  modification, are permitted provided that the following conditions

 -  are met:

 -  1. Redistributions of source code must retain the above copyright

 -     notice, this list of conditions and the following disclaimer.

 -  2. Redistributions in binary form must reproduce the above

 -     copyright notice, this list of conditions and the following

 -     disclaimer in the documentation and/or other materials

 -     provided with the distribution.

 -

 -  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

 -  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

 -  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

 -  A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL ANY

 -  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

 -  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

 -  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

 -  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY

 -  OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING

 -  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

 -  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 *====================================================================*/

/*!

 * \file runlength.c

 * <pre>

 *

 *     Label pixels by membership in runs

 *           PIX         *pixStrokeWidthTransform()

 *           static PIX  *pixFindMinRunsOrthogonal()

 *           PIX         *pixRunlengthTransform()

 *

 *     Find runs along horizontal and vertical lines

 *           l_int32      pixFindHorizontalRuns()

 *           l_int32      pixFindVerticalRuns()

 *

 *     Find max runs along horizontal and vertical lines

 *           l_int32      pixFindMaxRuns()

 *           l_int32      pixFindMaxHorizontalRunOnLine()

 *           l_int32      pixFindMaxVerticalRunOnLine()

 *

 *     Compute runlength-to-membership transform on a line

 *           l_int32      runlengthMembershipOnLine()

 *

 *     Make byte position LUT

 *           l_int32      makeMSBitLocTab()

 *

 *  Here we're handling runs of either black or white pixels on 1 bpp

 *  images.  The directions of the runs in the stroke width transform

 *  are selectable from given sets of angles.  Most of the other runs

 *  are oriented either horizontally along the raster lines or

 *  vertically along pixel columns.

 * </pre>

 */

#ifdef HAVE_CONFIG_H

#include <config_auto.h>

#endif  /* HAVE_CONFIG_H */

#include <string.h>

#include <math.h>

#include "allheaders.h"

static PIX *pixFindMinRunsOrthogonal(PIX *pixs, l_float32 angle, l_int32 depth);

/*-----------------------------------------------------------------------*

 *                   Label pixels by membership in runs                  *

 *-----------------------------------------------------------------------*/

/*!

 * \brief   pixStrokeWidthTransform()

 *

 * \param[in]     pixs      1 bpp

 * \param[in]     color     0 for white runs, 1 for black runs

 * \param[in]     depth     of pixd: 8 or 16 bpp

 * \param[in]     nangles   2, 4, 6 or 8

 * \return   pixd   8 or 16 bpp, or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) The dest Pix is 8 or 16 bpp, with the pixel values

 *          equal to the stroke width in which it is a member.

 *          The values are clipped to the max pixel value if necessary.

 *      (2) %color determines if we're labelling white or black strokes.

 *      (3) A pixel that is not a member of the chosen color gets

 *          value 0; it belongs to a width of length 0 of the

 *          chosen color.

 *      (4) This chooses, for each dest pixel, the minimum of sets

 *          of runlengths through each pixel.  Here are the sets:

 *            nangles    increment          set

 *            -------    ---------    --------------------------------

 *               2          90       {0, 90}

 *               4          45       {0, 45, 90, 135}

 *               6          30       {0, 30, 60, 90, 120, 150}

 *               8          22.5     {0, 22.5, 45, 67.5, 90, 112.5, 135, 157.5}

 *      (5) Runtime scales linearly with (%nangles - 2).

 * </pre>

 */

PIX *

pixStrokeWidthTransform(PIX     *pixs,

                        l_int32  color,

                        l_int32  depth,

                        l_int32  nangles)

{

l_float32  angle, pi;

PIX       *pixh, *pixv, *pixt, *pixg1, *pixg2, *pixg3, *pixg4;

    if (!pixs || pixGetDepth(pixs) != 1)

        return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);

    if (depth != 8 && depth != 16)

        return (PIX *)ERROR_PTR("depth must be 8 or 16 bpp", __func__, NULL);

    if (nangles != 2 && nangles != 4 && nangles != 6 && nangles != 8)

        return (PIX *)ERROR_PTR("nangles not in {2,4,6,8}", __func__, NULL);

        /* Use fg runs for evaluation */

    if (color == 0)

        pixt = pixInvert(NULL, pixs);

    else

        pixt = pixClone(pixs);

        /* Find min length at 0 and 90 degrees */

    pixh = pixRunlengthTransform(pixt, 1, L_HORIZONTAL_RUNS, depth);

    pixv = pixRunlengthTransform(pixt, 1, L_VERTICAL_RUNS, depth);

    pixg1 = pixMinOrMax(NULL, pixh, pixv, L_CHOOSE_MIN);

    pixDestroy(&pixh);

    pixDestroy(&pixv);

    pixg2 = pixg3 = pixg4 = NULL;

    pi = 3.1415926535f;

    if (nangles == 4 || nangles == 8) {

            /* Find min length at +45 and -45 degrees */

        angle = pi / 4.0f;

        pixg2 = pixFindMinRunsOrthogonal(pixt, angle, depth);

    }

    if (nangles == 6) {

            /* Find min length at +30 and -60 degrees */

        angle = pi / 6.0f;

        pixg2 = pixFindMinRunsOrthogonal(pixt, angle, depth);

            /* Find min length at +60 and -30 degrees */

        angle = pi / 3.0f;

        pixg3 = pixFindMinRunsOrthogonal(pixt, angle, depth);

    }

    if (nangles == 8) {

            /* Find min length at +22.5 and -67.5 degrees */

        angle = pi / 8.0f;

        pixg3 = pixFindMinRunsOrthogonal(pixt, angle, depth);

            /* Find min length at +67.5 and -22.5 degrees */

        angle = 3.0 * pi / 8.0f;

        pixg4 = pixFindMinRunsOrthogonal(pixt, angle, depth);

    }

    pixDestroy(&pixt);

    if (nangles > 2)

        pixMinOrMax(pixg1, pixg1, pixg2, L_CHOOSE_MIN);

    if (nangles > 4)

        pixMinOrMax(pixg1, pixg1, pixg3, L_CHOOSE_MIN);

    if (nangles > 6)

        pixMinOrMax(pixg1, pixg1, pixg4, L_CHOOSE_MIN);

    pixDestroy(&pixg2);

    pixDestroy(&pixg3);

    pixDestroy(&pixg4);

    return pixg1;

}

/*!

 * \brief   pixFindMinRunsOrthogonal()

 *

 * \param[in]     pixs     1 bpp

 * \param[in]     angle    in radians

 * \param[in]     depth    of pixd: 8 or 16 bpp

 * \return   pixd 8 or 16 bpp, or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) This computes, for each fg pixel in pixs, the minimum of

 *          the runlengths going through that pixel in two orthogonal

 *          directions: at %angle and at (90 + %angle).

 *      (2) We use rotation by shear because the forward and backward

 *          rotations by the same angle are exact inverse operations.

 *          As a result, the nonzero pixels in pixd correspond exactly

 *          to the fg pixels in pixs.  This is not the case with

 *          sampled rotation, due to spatial quantization.  Nevertheless,

 *          the result suffers from lack of exact correspondence

 *          between original and rotated pixels, also due to spatial

 *          quantization, causing some boundary pixels to be

 *          shifted from bg to fg or v.v.

 * </pre>

 */

static PIX *

pixFindMinRunsOrthogonal(PIX       *pixs,

                         l_float32  angle,

                         l_int32    depth)

{

l_int32  w, h, diag, xoff, yoff;

PIX     *pixb, *pixr, *pixh, *pixv, *pixg1, *pixg2, *pixd;

BOX     *box;

    if (!pixs || pixGetDepth(pixs) != 1)

        return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);

        /* Rasterop into the center of a sufficiently large image

         * so we don't lose pixels for any rotation angle. */

    pixGetDimensions(pixs, &w, &h, NULL);

    diag = (l_int32)(sqrt((l_float64)(w * w + h * h)) + 2.5);

    xoff = (diag - w) / 2;

    yoff = (diag - h) / 2;

    pixb = pixCreate(diag, diag, 1);

    pixRasterop(pixb, xoff, yoff, w, h, PIX_SRC, pixs, 0, 0);

        /* Rotate about the 'center', get the min of orthogonal transforms,

         * rotate back, and crop the part corresponding to pixs.  */

    pixr = pixRotateShear(pixb, diag / 2, diag / 2, angle, L_BRING_IN_WHITE);

    pixh = pixRunlengthTransform(pixr, 1, L_HORIZONTAL_RUNS, depth);

    pixv = pixRunlengthTransform(pixr, 1, L_VERTICAL_RUNS, depth);

    pixg1 = pixMinOrMax(NULL, pixh, pixv, L_CHOOSE_MIN);

    pixg2 = pixRotateShear(pixg1, diag / 2, diag / 2, -angle, L_BRING_IN_WHITE);

    box = boxCreate(xoff, yoff, w, h);

    pixd = pixClipRectangle(pixg2, box, NULL);

    pixDestroy(&pixb);

    pixDestroy(&pixr);

    pixDestroy(&pixh);

    pixDestroy(&pixv);

    pixDestroy(&pixg1);

    pixDestroy(&pixg2);

    boxDestroy(&box);

    return pixd;

}

/*!

 * \brief   pixRunlengthTransform()

 *

 * \param[in]     pixs        1 bpp

 * \param[in]     color       0 for white runs, 1 for black runs

 * \param[in]     direction   L_HORIZONTAL_RUNS, L_VERTICAL_RUNS

 * \param[in]     depth       8 or 16 bpp

 * \return   pixd   8 or 16 bpp, or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) The dest Pix is 8 or 16 bpp, with the pixel values

 *          equal to the runlength in which it is a member.

 *          The length is clipped to the max pixel value if necessary.

 *      (2) %color determines if we're labelling white or black runs.

 *      (3) A pixel that is not a member of the chosen color gets

 *          value 0; it belongs to a run of length 0 of the

 *          chosen color.

 *      (4) To convert for maximum dynamic range, either linear or

 *          log, use pixMaxDynamicRange().

 * </pre>

 */

PIX *

pixRunlengthTransform(PIX     *pixs,

                      l_int32  color,

                      l_int32  direction,

                      l_int32  depth)

{

l_int32    i, j, w, h, wpld, bufsize, maxsize, n;

l_int32   *start, *end, *buffer;

l_uint32  *datad, *lined;

PIX       *pixt, *pixd;

    if (!pixs)

        return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);

    if (pixGetDepth(pixs) != 1)

        return (PIX *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);

    if (depth != 8 && depth != 16)

        return (PIX *)ERROR_PTR("depth must be 8 or 16 bpp", __func__, NULL);

    pixGetDimensions(pixs, &w, &h, NULL);

    if (direction == L_HORIZONTAL_RUNS)

        maxsize = 1 + w / 2;

    else if (direction == L_VERTICAL_RUNS)

        maxsize = 1 + h / 2;

    else

        return (PIX *)ERROR_PTR("invalid direction", __func__, NULL);

    bufsize = L_MAX(w, h);

    if (bufsize > 1000000) {

        L_ERROR("largest image dimension = %d; too big\n", __func__, bufsize);

        return NULL;

    }

    if ((pixd = pixCreate(w, h, depth)) == NULL)

        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);

    datad = pixGetData(pixd);

    wpld = pixGetWpl(pixd);

    start = (l_int32 *)LEPT_CALLOC(maxsize, sizeof(l_int32));

    end = (l_int32 *)LEPT_CALLOC(maxsize, sizeof(l_int32));

    buffer = (l_int32 *)LEPT_CALLOC(bufsize, sizeof(l_int32));

        /* Use fg runs for evaluation */

    if (color == 0)

        pixt = pixInvert(NULL, pixs);

    else

        pixt = pixClone(pixs);

    if (direction == L_HORIZONTAL_RUNS) {

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

            pixFindHorizontalRuns(pixt, i, start, end, &n);

            runlengthMembershipOnLine(buffer, w, depth, start, end, n);

            lined = datad + i * wpld;

            if (depth == 8) {

                for (j = 0; j < w; j++)

                    SET_DATA_BYTE(lined, j, buffer[j]);

            } else {  /* depth == 16 */

                for (j = 0; j < w; j++)

                    SET_DATA_TWO_BYTES(lined, j, buffer[j]);

            }

        }

    } else {  /* L_VERTICAL_RUNS */

        for (j = 0; j < w; j++) {

            pixFindVerticalRuns(pixt, j, start, end, &n);

            runlengthMembershipOnLine(buffer, h, depth, start, end, n);

            if (depth == 8) {

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

                    lined = datad + i * wpld;

                    SET_DATA_BYTE(lined, j, buffer[i]);

                }

            } else {  /* depth == 16 */

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

                    lined = datad + i * wpld;

                    SET_DATA_TWO_BYTES(lined, j, buffer[i]);

                }

            }

        }

    }

    pixDestroy(&pixt);

    LEPT_FREE(start);

    LEPT_FREE(end);

    LEPT_FREE(buffer);

    return pixd;

}

/*-----------------------------------------------------------------------*

 *               Find runs along horizontal and vertical lines           *

 *-----------------------------------------------------------------------*/

/*!

 * \brief   pixFindHorizontalRuns()

 *

 * \param[in]    pix      1 bpp

 * \param[in]    y        line to traverse

 * \param[in]    xstart   returns array of start positions for fg runs

 * \param[in]    xend     returns array of end positions for fg runs

 * \param[out]   pn       the number of runs found

 * \return  0 if OK; 1 on error

 *

 * <pre>

 * Notes:

 *      (1) This finds foreground horizontal runs on a single scanline.

 *      (2) To find background runs, use pixInvert() before applying

 *          this function.

 *      (3) %xstart and %xend arrays are input.  They should be

 *          of size w/2 + 1 to insure that they can hold

 *          the maximum number of runs in the raster line.

 * </pre>

 */

l_ok

pixFindHorizontalRuns(PIX      *pix,

                      l_int32   y,

                      l_int32  *xstart,

                      l_int32  *xend,

                      l_int32  *pn)

{

l_int32    inrun;  /* boolean */

l_int32    index, w, h, d, j, wpl, val;

l_uint32  *line;

    if (!pn)

        return ERROR_INT("&n not defined", __func__, 1);

    *pn = 0;

    if (!pix)

        return ERROR_INT("pix not defined", __func__, 1);

    pixGetDimensions(pix, &w, &h, &d);

    if (d != 1)

        return ERROR_INT("pix not 1 bpp", __func__, 1);

    if (y < 0 || y >= h)

        return ERROR_INT("y not in [0 ... h - 1]", __func__, 1);

    if (!xstart)

        return ERROR_INT("xstart not defined", __func__, 1);

    if (!xend)

        return ERROR_INT("xend not defined", __func__, 1);

    wpl = pixGetWpl(pix);

    line = pixGetData(pix) + y * wpl;

    inrun = FALSE;

    index = 0;

    for (j = 0; j < w; j++) {

        val = GET_DATA_BIT(line, j);

        if (!inrun) {

            if (val) {

                xstart[index] = j;

                inrun = TRUE;

            }

        } else {

            if (!val) {

                xend[index++] = j - 1;

                inrun = FALSE;

            }

        }

    }

        /* Finish last run if necessary */

    if (inrun)

        xend[index++] = w - 1;

    *pn = index;

    return 0;

}

/*!

 * \brief   pixFindVerticalRuns()

 *

 * \param[in]    pix      1 bpp

 * \param[in]    x        line to traverse

 * \param[in]    ystart   returns array of start positions for fg runs

 * \param[in]    yend     returns array of end positions for fg runs

 * \param[out]   pn       the number of runs found

 * \return  0 if OK; 1 on error

 *

 * <pre>

 * Notes:

 *      (1) This finds foreground vertical runs on a single scanline.

 *      (2) To find background runs, use pixInvert() before applying

 *          this function.

 *      (3) %ystart and %yend arrays are input.  They should be

 *          of size h/2 + 1 to insure that they can hold

 *          the maximum number of runs in the raster line.

 * </pre>

 */

l_ok

pixFindVerticalRuns(PIX      *pix,

                    l_int32   x,

                    l_int32  *ystart,

                    l_int32  *yend,

                    l_int32  *pn)

{

l_int32    inrun;  /* boolean */

l_int32    index, w, h, d, i, wpl, val;

l_uint32  *data, *line;

    if (!pn)

        return ERROR_INT("&n not defined", __func__, 1);

    *pn = 0;

    if (!pix)

        return ERROR_INT("pix not defined", __func__, 1);

    pixGetDimensions(pix, &w, &h, &d);

    if (d != 1)

        return ERROR_INT("pix not 1 bpp", __func__, 1);

    if (x < 0 || x >= w)

        return ERROR_INT("x not in [0 ... w - 1]", __func__, 1);

    if (!ystart)

        return ERROR_INT("ystart not defined", __func__, 1);

    if (!yend)

        return ERROR_INT("yend not defined", __func__, 1);

    wpl = pixGetWpl(pix);

    data = pixGetData(pix);

    inrun = FALSE;

    index = 0;

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

        line = data + i * wpl;

        val = GET_DATA_BIT(line, x);

        if (!inrun) {

            if (val) {

                ystart[index] = i;

                inrun = TRUE;

            }

        } else {

            if (!val) {

                yend[index++] = i - 1;

                inrun = FALSE;

            }

        }

    }

        /* Finish last run if necessary */

    if (inrun)

        yend[index++] = h - 1;

    *pn = index;

    return 0;

}

/*-----------------------------------------------------------------------*

 *            Find max runs along horizontal and vertical lines          *

 *-----------------------------------------------------------------------*/

/*!

 * \brief   pixFindMaxRuns()

 *

 * \param[in]    pix         1 bpp

 * \param[in]    direction   L_HORIZONTAL_RUNS or L_VERTICAL_RUNS

 * \param[out]   pnastart    [optional] start locations of longest runs

 * \return  na of lengths of runs, or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) This finds the longest foreground runs by row or column

 *      (2) To find background runs, use pixInvert() before applying

 *          this function.

 * </pre>

 */

NUMA *

pixFindMaxRuns(PIX     *pix,

               l_int32  direction,

               NUMA   **pnastart)

{

l_int32  w, h, i, start, size;

NUMA    *nasize;

    if (pnastart) *pnastart = NULL;

    if (direction != L_HORIZONTAL_RUNS && direction != L_VERTICAL_RUNS)

        return (NUMA *)ERROR_PTR("direction invalid", __func__, NULL);

    if (!pix || pixGetDepth(pix) != 1)

        return (NUMA *)ERROR_PTR("pix undefined or not 1 bpp", __func__, NULL);

    pixGetDimensions(pix, &w, &h, NULL);

    nasize = numaCreate(w);

    if (pnastart) *pnastart = numaCreate(w);

    if (direction == L_HORIZONTAL_RUNS) {

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

            pixFindMaxHorizontalRunOnLine(pix, i, &start, &size);

            numaAddNumber(nasize, size);

            if (pnastart) numaAddNumber(*pnastart, start);

        }

    } else {  /* vertical scans */

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

            pixFindMaxVerticalRunOnLine(pix, i, &start, &size);

            numaAddNumber(nasize, size);

            if (pnastart) numaAddNumber(*pnastart, start);

        }

    }

    return nasize;

}

/*!

 * \brief   pixFindMaxHorizontalRunOnLine()

 *

 * \param[in]    pix       1 bpp

 * \param[in]    y         line to traverse

 * \param[out]   pxstart   [optional] start position

 * \param[out]   psize     the size of the run

 * \return  0 if OK; 1 on error

 *

 * <pre>

 * Notes:

 *      (1) This finds the longest foreground horizontal run on a scanline.

 *      (2) To find background runs, use pixInvert() before applying

 *          this function.

 * </pre>

 */

l_ok

pixFindMaxHorizontalRunOnLine(PIX      *pix,

                              l_int32   y,

                              l_int32  *pxstart,

                              l_int32  *psize)

{

l_int32    inrun;  /* boolean */

l_int32    w, h, j, wpl, val, maxstart, maxsize, length, start;

l_uint32  *line;

    if (pxstart) *pxstart = 0;

    if (!psize)

        return ERROR_INT("&size not defined", __func__, 1);

    *psize = 0;

    if (!pix || pixGetDepth(pix) != 1)

        return ERROR_INT("pix not defined or not 1 bpp", __func__, 1);

    pixGetDimensions(pix, &w, &h, NULL);

    if (y < 0 || y >= h)

        return ERROR_INT("y not in [0 ... h - 1]", __func__, 1);

    wpl = pixGetWpl(pix);

    line = pixGetData(pix) + y * wpl;

    inrun = FALSE;

    start = 0;

    maxstart = 0;

    maxsize = 0;

    for (j = 0; j < w; j++) {

        val = GET_DATA_BIT(line, j);

        if (!inrun) {

            if (val) {

                start = j;

                inrun = TRUE;

            }

        } else if (!val) {  /* run just ended */

            length = j - start;

            if (length > maxsize) {

                maxsize = length;

                maxstart = start;

            }

            inrun = FALSE;

        }

    }

    if (inrun) {  /* a run has continued to the end of the row */

        length = j - start;

        if (length > maxsize) {

            maxsize = length;

            maxstart = start;

        }

    }

    if (pxstart) *pxstart = maxstart;

    *psize = maxsize;

    return 0;

}

/*!

 * \brief   pixFindMaxVerticalRunOnLine()

 *

 * \param[in]    pix       1 bpp

 * \param[in]    x         column to traverse

 * \param[out]   pystart   [optional] start position

 * \param[out]   psize     the size of the run

 * \return  0 if OK; 1 on error

 *

 * <pre>

 * Notes:

 *      (1) This finds the longest foreground vertical run on a scanline.

 *      (2) To find background runs, use pixInvert() before applying

 *          this function.

 * </pre>

 */

l_ok

pixFindMaxVerticalRunOnLine(PIX      *pix,

                            l_int32   x,

                            l_int32  *pystart,

                            l_int32  *psize)

{

l_int32    inrun;  /* boolean */

l_int32    w, h, i, wpl, val, maxstart, maxsize, length, start;

l_uint32  *data, *line;

    if (pystart) *pystart = 0;

    if (!psize)

        return ERROR_INT("&size not defined", __func__, 1);

    *psize = 0;

    if (!pix || pixGetDepth(pix) != 1)

        return ERROR_INT("pix not defined or not 1 bpp", __func__, 1);

    pixGetDimensions(pix, &w, &h, NULL);

    if (x < 0 || x >= w)

        return ERROR_INT("x not in [0 ... w - 1]", __func__, 1);

    wpl = pixGetWpl(pix);

    data = pixGetData(pix);

    inrun = FALSE;

    start = 0;

    maxstart = 0;

    maxsize = 0;

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

        line = data + i * wpl;

        val = GET_DATA_BIT(line, x);

        if (!inrun) {

            if (val) {

                start = i;

                inrun = TRUE;

            }

        } else if (!val) {  /* run just ended */

            length = i - start;

            if (length > maxsize) {

                maxsize = length;

                maxstart = start;

            }

            inrun = FALSE;

        }

    }

    if (inrun) {  /* a run has continued to the end of the column */

        length = i - start;

        if (length > maxsize) {

            maxsize = length;

            maxstart = start;

        }

    }

    if (pystart) *pystart = maxstart;

    *psize = maxsize;

    return 0;

}

/*-----------------------------------------------------------------------*

 *            Compute runlength-to-membership transform on a line        *

 *-----------------------------------------------------------------------*/

/*!

 * \brief   runlengthMembershipOnLine()

 *

 * \param[in]     buffer   into which full line of data is placed

 * \param[in]     size     full size of line; w or h

 * \param[in]     depth    8 or 16 bpp

 * \param[in]     start    array of start positions for fg runs

 * \param[in]     end      array of end positions for fg runs

 * \param[in]     n        the number of runs

 * \return   0 if OK; 1 on error

 *

 * <pre>

 * Notes:

 *      (1) Converts a set of runlengths into a buffer of

 *          runlength membership values.

 *      (2) Initialization of the array gives pixels that are

 *          not within a run the value 0.

 * </pre>

 */

l_ok

runlengthMembershipOnLine(l_int32  *buffer,

                          l_int32   size,

                          l_int32   depth,

                          l_int32  *start,

                          l_int32  *end,

                          l_int32   n)

{

l_int32  i, j, first, last, diff, max;

    if (!buffer)

        return ERROR_INT("buffer not defined", __func__, 1);

    if (!start)

        return ERROR_INT("start not defined", __func__, 1);

    if (!end)

        return ERROR_INT("end not defined", __func__, 1);

    if (depth == 8)

        max = 0xff;

    else  /* depth == 16 */

        max = 0xffff;

    memset(buffer, 0, 4 * size);

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

        first = start[i];

        last = end[i];

        diff = last - first + 1;

        diff = L_MIN(diff, max);

        for (j = first; j <= last; j++)

            buffer[j] = diff;

    }

    return 0;

}

/*-----------------------------------------------------------------------*

 *                       Make byte position LUT                          *

 *-----------------------------------------------------------------------*/

/*!

 * \brief   makeMSBitLocTab()

 *

 * \param[in]    bitval   either 0 or 1

 * \return  table:  for an input byte, the MS bit location, starting at 0

 *                  with the MSBit in the byte, or NULL on error.

 *

 * <pre>

 * Notes:

 *      (1) If %bitval == 1, it finds the leftmost ON pixel in a byte;

 *          otherwise if %bitval == 0, it finds the leftmost OFF pixel.

 *      (2) If there are no pixels of the indicated color in the byte,

 *          this returns 8.

 * </pre>

 */

l_int32 *

makeMSBitLocTab(l_int32  bitval)

{

l_int32   i, j;

l_int32  *tab;

l_uint8   byte, mask;

    tab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));

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

        byte = (l_uint8)i;

        if (bitval == 0)

            byte = ~byte;

        tab[i] = 8;

        mask = 0x80;

        for (j = 0; j < 8; j++) {

            if (byte & mask) {

                tab[i] = j;

                break;

            }

            mask >>= 1;

        }

    }

    return tab;

}