fribidi.c

share BIDI DEMO code

/* FriBidi - Library of BiDi algorithm
 * Copyright (C) 1999 Dov Grobgeld
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
#include <glib.h>
#include "fribidi.h"
#ifndef NO_STDIO
#include <stdio.h>
#endif

#ifndef NO_STDIO
#define DBG(s) if (fribidi_debug) { fprintf(stderr, s); }
#else
#define DBG(s)
#endif

/*======================================================================
// Typedef for the run-length list.
//----------------------------------------------------------------------*/
typedef struct _TypeLink TypeLink;

struct _TypeLink {
  TypeLink *prev;
  TypeLink *next;
  FriBidiCharType type;
  gint pos;
  gint len;
  gint level;
};

typedef struct {
  FriBidiChar key;
  FriBidiChar value;
} key_value_t;

/* Global variables */
gboolean fribidi_debug = FALSE;

void fribidi_set_debug(gboolean debug)
{
  fribidi_debug = debug;
}

static gint bidi_string_strlen(FriBidiChar *str)
{
  gint len = 0;

  while(*str++)
    len++;
  
  return len;
}

static void bidi_string_reverse(FriBidiChar *str, gint len)
{
  gint i;
  for (i=0; i<len/2; i++)
    {
      FriBidiChar tmp = str[i];
      str[i] = str[len-1-i];
      str[len-1-i] = tmp;
    }
}

static void
int16_array_reverse(guint16 *arr, gint len)
{
  gint i;
  for (i=0; i<len/2; i++)
    {
      guint16 tmp = arr[i];
      arr[i] = arr[len-1-i];
      arr[len-1-i] = tmp;
    }
}

#ifndef USE_SIMPLE_MALLOC
static TypeLink *free_type_links = NULL;
#endif

static TypeLink *new_type_link(void)
{
  TypeLink *link;
  
#ifdef USE_SIMPLE_MALLOC
  link = g_malloc(sizeof(TypeLink));
#else
  if (free_type_links)
    {
      link = free_type_links;
      free_type_links = free_type_links->next;
    }
  else
    {
      static GMemChunk *mem_chunk = NULL;

      if (!mem_chunk)
       mem_chunk = g_mem_chunk_new ("TypeLinkList",
                                    sizeof (TypeLink),
                                    sizeof (TypeLink) * 128,
                                    G_ALLOC_ONLY);

      link = g_chunk_new (TypeLink, mem_chunk);
    }
#endif
  
  link->len = 0;
  link->pos = 0;
  link->level = 0;
  link->next = NULL;
  link->prev = NULL;
  return link;
}

static void free_type_link(TypeLink *link)
{
#ifdef USE_SIMPLE_MALLOC
  g_free(link);
#else
  link->next = free_type_links;
  free_type_links = link;
#endif
}

static TypeLink *run_length_encode_types(gint *char_type, gint type_len)
{
  TypeLink *list = NULL;
  TypeLink *last;
  TypeLink *link;
  FriBidiCharType type;
  gint len, pos, i;

  /* Add the starting link */
  list = new_type_link();
  list->type = FRIBIDI_TYPE_SOT;
  list->len = 0;
  list->pos = 0;
  last = list;

  /* Sweep over the string_types */
  type = -1;
  len = 0;
  pos = -1;
  for (i=0; i<=type_len; i++)
    {
      if (i==type_len || char_type[i] != type)
	{
	  if (pos>=0)
	    {
	      link = new_type_link();
	      link->type = type;
	      link->pos = pos;
	      link->len = len;
             last->next = link;
             link->prev = last;
	      last = last->next;
	    }
	  if (i==type_len)
	    break;
	  len = 0;
	  pos = i;
	}
      type =char_type[i];
      len++;
    }

  /* Add the ending link */
  link = new_type_link();
  link->type = FRIBIDI_TYPE_EOT;
  link->len = 0;
  link->pos = type_len;
  last->next = link;
  link->prev = last;

  return list;
}

/* Some convenience macros */
#define RL_TYPE(list) (list)->type
#define RL_LEN(list) (list)->len
#define RL_POS(list) (list)->pos
#define RL_LEVEL(list) (list)->level

static void compact_list(TypeLink *list)
{
  while(list)
    {
      if (list->prev
	  && RL_TYPE(list->prev) == RL_TYPE(list))
	{
          TypeLink *next = list->next;
	  list->prev->next = list->next;
	  list->next->prev = list->prev;
	  RL_LEN(list->prev) = RL_LEN(list->prev) + RL_LEN(list);
          free_type_link(list);
	  list = next;
      }
      else
	list = list->next;
    }
}

/* Define a rule macro */

/* Rules for overriding current type */
#define TYPE_RULE1(old_this,            \
		   new_this)             \
     if (this_type == TYPE_ ## old_this)      \
         RL_TYPE(pp) =       FRIBIDI_TYPE_ ## new_this; \

/* Rules for current and previous type */
#define TYPE_RULE2(old_prev, old_this,            \
		  new_prev, new_this)             \
     if (    prev_type == FRIBIDI_TYPE_ ## old_prev       \
	  && this_type == FRIBIDI_TYPE_ ## old_this)      \
       {                                          \
	   RL_TYPE(pp->prev) = FRIBIDI_TYPE_ ## new_prev; \
	   RL_TYPE(pp) =       FRIBIDI_TYPE_ ## new_this; \
           continue;                              \
       }

/* A full rule that assigns all three types */
#define TYPE_RULE(old_prev, old_this, old_next,   \
		  new_prev, new_this, new_next)   \
     if (    prev_type == FRIBIDI_TYPE_ ## old_prev       \
	  && this_type == FRIBIDI_TYPE_ ## old_this       \
	  && next_type == FRIBIDI_TYPE_ ## old_next)      \
       {                                          \
	   RL_TYPE(pp->prev) = FRIBIDI_TYPE_ ## new_prev; \
	   RL_TYPE(pp) =       FRIBIDI_TYPE_ ## new_this; \
	   RL_TYPE(pp->next) = FRIBIDI_TYPE_ ## new_next; \
           continue;                              \
       }

/* For optimization the following macro only assigns the center type */
#define TYPE_RULE_C(old_prev, old_this, old_next,   \
		    new_this)   \
     if (    prev_type == FRIBIDI_TYPE_ ## old_prev       \
	  && this_type == FRIBIDI_TYPE_ ## old_this       \
	  && next_type == FRIBIDI_TYPE_ ## old_next)      \
       {                                          \
	   RL_TYPE(pp) =       FRIBIDI_TYPE_ ## new_this; \
           continue;                              \
       }

/*======================================================================
//  For debugging, define some macros for printing the types and the
//  levels.
//----------------------------------------------------------------------*/
#ifndef NO_STDIO
static void print_types_re(TypeLink *pp)
{
  while(pp)
    {
      printf("%d:%c(%d)[%d] ", RL_POS(pp), RL_TYPE(pp), RL_LEN(pp), RL_LEVEL(pp));
      pp = pp->next;
    }
  printf("\n");
}

static void print_resolved_levels(TypeLink *pp)
{
  while(pp)
    {
      gint i;
      for (i=0; i<RL_LEN(pp); i++)
	printf("%d", RL_LEVEL(pp));
      pp = pp->next;
    }
  printf("\n");
}

static void print_resolved_types(TypeLink *pp)
{
  while(pp)
    {
      gint i;
      for (i=0; i<RL_LEN(pp); i++)
	{
	  gchar ch;
	  FriBidiCharType type = RL_TYPE(pp);
         
	  /* Convert the type to something readable */
	  if (type == FRIBIDI_TYPE_R)
	    ch = 'R';
	  else if (type == FRIBIDI_TYPE_L)
	    ch = 'L';
	  else if (type == FRIBIDI_TYPE_E)
	    ch = 'E';
	  else if (type == FRIBIDI_TYPE_EN)
	    ch = 'n';
	  else if (type == FRIBIDI_TYPE_N)
	    ch = 'N';
	  else
	    ch = '?';
	  
	  printf("%c", ch);
	}
      pp = pp->next;
    }
  printf("\n");
}

static void print_bidi_string(FriBidiChar *str)
{
  gint i;
  for (i=0; i<bidi_string_strlen(str); i++)
    printf("%c", str[i]);
  printf("\n");
}
#endif

/*======================================================================
//  search_rl_for strong searches the run length list in the direction
//  indicated by dir for a strong directional. It returns a pointer to
//  the found character or NULL if none is found. */
//----------------------------------------------------------------------*/
static TypeLink *
search_rl_for_strong(TypeLink *pos,
		     gint  dir)
{
  TypeLink *pp = pos;

  if (dir == -1)
    {
      for (pp = pos; pp; pp=pp->prev)
	{
	  FriBidiCharType char_type = RL_TYPE(pp);
	  if (char_type == FRIBIDI_TYPE_R || char_type == FRIBIDI_TYPE_L)
	    return pp;
	}
    }
  else
    {
      for (pp = pos; pp; pp=pp->next)
	{
	  FriBidiCharType char_type = RL_TYPE(pp);
	  if (char_type == FRIBIDI_TYPE_R || char_type == FRIBIDI_TYPE_L)
	    return pp;
	}
    }
  return NULL;
}

/*======================================================================
//  This function should follow the Unicode specification closely!
//
//  It is still lacking the support for <RLO> and <LRO>.
//----------------------------------------------------------------------*/
static void
fribidi_analyse_string(/* input */
		       FriBidiChar *str,
		       gint len,
		       FriBidiCharType *pbase_dir,
		       /* output */
                      TypeLink **ptype_rl_list,
		       gint *pmax_level)
{
  gint base_level, base_dir;
  gint max_level;
  gint i;
  gint *char_type;
  gint prev_last_strong, last_strong;
  TypeLink *type_rl_list, *pp;

  /* Determinate character types */
  char_type = g_new(gint, len);
  for (i=0; i<len; i++)
    char_type[i] = fribidi_get_type(str[i]);

  /* Run length encode the character types */
  type_rl_list = run_length_encode_types(char_type, len);
  g_free(char_type);

  /* Find the base level */
  if (*pbase_dir == FRIBIDI_TYPE_L)
    {
      base_dir = FRIBIDI_TYPE_L;
      base_level = 0;
    }
  else if (*pbase_dir == FRIBIDI_TYPE_R)
    {
      base_dir = FRIBIDI_TYPE_R;
      base_level = 1;
    }

  /* Search for first strong character and use its direction as base
     direciton */
  else
    {
      base_level = 0; /* Default */
      base_dir = FRIBIDI_TYPE_N;
      for (pp = type_rl_list; pp; pp = pp->next)
	{
	  if (RL_TYPE(pp) == FRIBIDI_TYPE_R)
	    {
	      base_level = 1;
	      base_dir = FRIBIDI_TYPE_R;
	      break;