ucsset.c   [plain text]

#ifndef lint
static char *rcsid = "$Id: ucsset.c,v 1.1 2003/06/04 00:26:15 marka Exp $";
#endif

/*
 * Copyright (c) 2001 Japan Network Information Center.  All rights reserved.
 *  
 * By using this file, you agree to the terms and conditions set forth bellow.
 * 
 * 			LICENSE TERMS AND CONDITIONS 
 * 
 * The following License Terms and Conditions apply, unless a different
 * license is obtained from Japan Network Information Center ("JPNIC"),
 * a Japanese association, Kokusai-Kougyou-Kanda Bldg 6F, 2-3-4 Uchi-Kanda,
 * Chiyoda-ku, Tokyo 101-0047, Japan.
 * 
 * 1. Use, Modification and Redistribution (including distribution of any
 *    modified or derived work) in source and/or binary forms is permitted
 *    under this License Terms and Conditions.
 * 
 * 2. Redistribution of source code must retain the copyright notices as they
 *    appear in each source code file, this License Terms and Conditions.
 * 
 * 3. Redistribution in binary form must reproduce the Copyright Notice,
 *    this License Terms and Conditions, in the documentation and/or other
 *    materials provided with the distribution.  For the purposes of binary
 *    distribution the "Copyright Notice" refers to the following language:
 *    "Copyright (c) 2000-2002 Japan Network Information Center.  All rights reserved."
 * 
 * 4. The name of JPNIC may not be used to endorse or promote products
 *    derived from this Software without specific prior written approval of
 *    JPNIC.
 * 
 * 5. Disclaimer/Limitation of Liability: THIS SOFTWARE IS PROVIDED BY JPNIC
 *    "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 JPNIC 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 DAMAGES.
 */

#include <config.h>

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include <idn/result.h>
#include <idn/assert.h>
#include <idn/logmacro.h>
#include <idn/ucsset.h>

#define UCS_MAX		0x80000000UL

#define INIT_SIZE	50

/*
 * Code point range.
 *
 * The set of code points is represented by an array of code point ranges.
 * In the building phase, specified ranges by 'idn_ucsset_add' or
 * 'idn_ucsset_addrange' are simply appended to the array.
 * And 'idn_ucsset_fix' sorts the array by the code point value, and also
 * merges any intersecting ranges.  Since the array is sorted, a binary
 * search can be used for looking up.
 */
typedef struct {
	unsigned long from;
	unsigned long to;
} range_t;

/*
 * Code point segment.
 *
 * To speed up searching further, the entire region of UCS-4 code points
 * (U+0000 - U+7FFFFFFF) are divided into segments. For each segment,
 * the first and last element of the range array corresponding to the
 * segment are computed by 'idn_ucsset_fix'.  This narrows down the
 * (initial) search range.
 */
typedef struct {
	int range_start;	/* index of ucsset.ranges */
	int range_end;		/* ditto */
} segment_t;

/*
 * Code point to segment index conversion.
 *
 * Below is the function that maps a code point to the corresponding segment.
 * The mapping is non-uniform, so that BMP, the following 16 planes that
 * comprise Unicode code points together with BMP, and other planes
 * have different granularity.
 */
#define SEG_THLD1	0x10000		/* BMP */
#define SEG_THLD2	0x110000	/* Unicode (BMP+16planes) */
#define SEG_SFT1	10		/* BMP: 1K code points/segment */
#define SEG_SFT2	14		/* following 16 planes: 16K cp/seg */
#define SEG_SFT3	24		/* rest: 16M cp/seg */
#define SEG_OFF1	(SEG_THLD1 >> SEG_SFT1)
#define SEG_OFF2	(((SEG_THLD2 - SEG_THLD1) >> SEG_SFT2) + SEG_OFF1)
#define SEG_INDEX(v) \
	(((v) < SEG_THLD1) ? ((v) >> SEG_SFT1) : \
	 ((v) < SEG_THLD2) ? ((((v) - SEG_THLD1) >> SEG_SFT2) + SEG_OFF1) : \
	 ((((v) - SEG_THLD2) >> SEG_SFT3) + SEG_OFF2))
#define SEG_LEN	(SEG_INDEX(UCS_MAX - 1) + 1)

/*
 * Representation of set of UCS code points.
 */
typedef struct idn_ucsset {
	segment_t segments[SEG_LEN];
	int fixed;
	int size;			/* allocated size of 'ranges' */
	int nranges;			/* num of ranges */
	range_t *ranges;
	int refcnt;			/* reference count */
} ucsset;

static idn_result_t	addrange(idn_ucsset_t ctx, unsigned long from,
				 unsigned long to, char *func_name);
static int		comp_range(const void *v1, const void *v2);

idn_result_t
idn_ucsset_create(idn_ucsset_t *ctx) {
	idn_ucsset_t bm;

	assert(ctx != NULL);

	TRACE(("idn_ucsset_create()\n"));

	if ((bm = malloc(sizeof(ucsset))) == NULL) {
		WARNING(("idn_ucsset_create: malloc failed\n"));
		return idn_nomemory;
	}
	bm->size = bm->nranges = 0;
	bm->ranges = NULL;
	bm->fixed = 0;
	bm->refcnt = 1;
	*ctx = bm;
	return (idn_success);
}

void
idn_ucsset_destroy(idn_ucsset_t ctx) {
	assert(ctx != NULL && ctx->refcnt > 0);

	TRACE(("idn_ucsset_destroy()\n"));

	if (--ctx->refcnt == 0) {
		if (ctx->ranges != NULL)
			free(ctx->ranges);
		free(ctx);
	}
}

void
idn_ucsset_incrref(idn_ucsset_t ctx) {
	assert(ctx != NULL && ctx->refcnt > 0);

	TRACE(("idn_ucsset_incrref()\n"));

	ctx->refcnt++;
}

idn_result_t
idn_ucsset_add(idn_ucsset_t ctx, unsigned long v) {
	assert(ctx != NULL && ctx->refcnt > 0);

	TRACE(("idn_ucsset_add(v=U+%lX)\n", v));

	return (addrange(ctx, v, v, "idn_ucsset_add"));
}

idn_result_t
idn_ucsset_addrange(idn_ucsset_t ctx, unsigned long from,
			 unsigned long to)
{
	assert(ctx != NULL && ctx->refcnt > 0);

	TRACE(("idn_ucsset_addrange(from=U+%lX, to=U+%lX)\n",
	       from, to));

	return (addrange(ctx, from, to, "idn_ucsset_addrange"));
}

void
idn_ucsset_fix(idn_ucsset_t ctx) {
	int nranges;
	range_t *ranges;
	segment_t *segments;
	int i, j;

	assert(ctx != NULL && ctx->refcnt > 0);

	TRACE(("idn_ucsset_fix()\n"));

	nranges = ctx->nranges;
	ranges = ctx->ranges;
	segments = ctx->segments;

	if (ctx->fixed)
		return;

	ctx->fixed = 1;

	/* Initialize segment array */
	for (i = 0; i < SEG_LEN; i++) {
		segments[i].range_start = -1;
		segments[i].range_end = -1;
	}

	/* If the set is empty, there's nothing to be done. */
	if (nranges == 0)
		return;

	/* Sort ranges. */
	qsort(ranges, nranges, sizeof(range_t), comp_range);

	/* Merge overlapped/continuous ranges. */
	for (i = 0, j = 1; j < nranges; j++) {
		if (ranges[i].to + 1 >= ranges[j].from) {
			/* can be merged */
			if (ranges[i].to < ranges[j].to) {
				ranges[i].to = ranges[j].to;
			}
		} else {
			i++;
			if (i < j)
				ranges[i] = ranges[j];
		}
	}
	/* 'i' points the last range in the array. */
	ctx->nranges = nranges = ++i;

	/* Create segment array. */
	for (i = 0; i < nranges; i++) {
		int fidx = SEG_INDEX(ranges[i].from);
		int tidx = SEG_INDEX(ranges[i].to);

		for (j = fidx; j <= tidx; j++) {
			if (segments[j].range_start < 0)
				segments[j].range_start = i;
			segments[j].range_end = i;
		}
	}

#if 0
	/*
	 * Does the standard guarantee realloc() always succeeds
	 * when shrinking?
	 */
	/* Shrink malloc'ed space if possible. */
	ctx->ranges = realloc(ctx->ranges, ctx->nranges * sizeof(range_t));
#endif
}

idn_result_t
idn_ucsset_lookup(idn_ucsset_t ctx, unsigned long v, int *found) {
	int idx;
	segment_t *segments;

	assert(ctx != NULL && ctx->refcnt > 0 && found != NULL);

	TRACE(("idn_ucsset_lookup(v=U+%lX)\n", v));

	/* Make sure it is fixed. */
	if (!ctx->fixed) {
		WARNING(("idn_ucsset_lookup: not fixed yet\n"));
		return (idn_failure);
	}

	/* Check the given code point. */
	if (v >= UCS_MAX)
		return (idn_invalid_codepoint);

	/* Get the segment 'v' belongs to. */
	segments = ctx->segments;
	idx = SEG_INDEX(v);

	/* Do binary search. */
	*found = 0;
	if (segments[idx].range_start >= 0) {
		int lo = segments[idx].range_start;
		int hi = segments[idx].range_end;
		range_t *ranges = ctx->ranges;

		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			if (v < ranges[mid].from) {
				hi = mid - 1;
			} else if (v > ranges[mid].to) {
				lo = mid + 1;
			} else {
				*found = 1;
				break;
			}
		}
	}
	return (idn_success);
}

static idn_result_t
addrange(idn_ucsset_t ctx, unsigned long from, unsigned long to,
	 char *func_name)
{
	range_t *newbuf;

	/* Check the given code points. */
	if (from > UCS_MAX) {
		WARNING(("%s: code point out of range (U+%lX)\n",
			 func_name, from));
		return (idn_invalid_codepoint);
	} else if (to > UCS_MAX) {
		WARNING(("%s: code point out of range (U+%lX)\n",
			 func_name, to));
		return (idn_invalid_codepoint);
	} else if (from > to) {
		WARNING(("%s: invalid range spec (U+%lX-U+%lX)\n",
			 func_name, from, to));
		return (idn_invalid_codepoint);
	}

	/* Make sure it is not fixed yet. */
	if (ctx->fixed) {
		WARNING(("%s: attempt to add to already fixed object\n",
			 func_name));
		return (idn_failure);
	}

	/* Append the specified range to the 'ranges' array. */
	if (ctx->nranges >= ctx->size) {
		/* Make it bigger. */
		if (ctx->size == 0)
			ctx->size = INIT_SIZE;
		else
			ctx->size *= 2;
		newbuf = realloc(ctx->ranges, ctx->size * sizeof(range_t));
		if (newbuf == NULL)
			return (idn_nomemory);
		ctx->ranges = newbuf;
	}
	ctx->ranges[ctx->nranges].from = from;
	ctx->ranges[ctx->nranges].to = to;
	ctx->nranges++;

	return (idn_success);
}

static int
comp_range(const void *v1, const void *v2) {
	/*
	 * Range comparation function suitable for qsort().
	 */
	const range_t *r1 = v1;
	const range_t *r2 = v2;

	if (r1->from < r2->from)
		return (-1);
	else if (r1->from > r2->from)
		return (1);
	else
		return (0);
}