svn merge ^/branches/released .

3 files changed, 3986 insertions, 3989 deletions

diff --git a/libX11/configure.ac b/libX11/configure.ac
index cfb8105c0..d09968b8e 100644
--- a/libX11/configure.ac
+++ b/libX11/configure.ac
@@ -1,490 +1,486 @@
-#                                               -*- Autoconf -*-

-# Process this file with autoconf to produce a configure script.

-

-AC_PREREQ(2.60)

-AC_INIT([libX11],

-        [1.4.1],

-        [https://bugs.freedesktop.org/enter_bug.cgi?product=xorg],

-        libX11)

-AC_CONFIG_SRCDIR([Makefile.am])

-AC_CONFIG_MACRO_DIR([m4])

-AC_CANONICAL_BUILD

-AC_CANONICAL_HOST

-

-AM_INIT_AUTOMAKE([foreign dist-bzip2])

-AM_MAINTAINER_MODE

-AM_CONFIG_HEADER([src/config.h])

-AC_CONFIG_HEADER([include/X11/XlibConf.h])

-

-# Set common system defines for POSIX extensions, such as _GNU_SOURCE

-# Must be called before any macros that run the compiler (like AC_PROG_LIBTOOL)

-# to avoid autoconf errors.

-AC_USE_SYSTEM_EXTENSIONS

-

-# Require xorg-macros minimum of 1.11 for disabling fop by default

-m4_ifndef([XORG_MACROS_VERSION],

-          [m4_fatal([must install xorg-macros 1.11 or later before running autoconf/autogen])])

-XORG_MACROS_VERSION(1.11)

-XORG_DEFAULT_OPTIONS

-XORG_ENABLE_SPECS

-XORG_WITH_XMLTO(0.0.20)

-XORG_WITH_FOP([no])

-XORG_CHECK_SGML_DOCTOOLS(1.5)

-XORG_PROG_RAWCPP

-

-# Checks for programs.

-AC_PROG_LIBTOOL

-AC_PROG_CC

-PKG_PROG_PKG_CONFIG

-

-if test x"$CC_FOR_BUILD" = x; then

-	if test x"$cross_compiling" = xyes; then

-	       AC_CHECK_PROGS(CC_FOR_BUILD, gcc cc)

-	else

-	       CC_FOR_BUILD="$CC"

-	fi

-fi

-AC_SUBST([CC_FOR_BUILD])

-

-if test x"$CPPFLAGS_FOR_BUILD" = x; then

-	if test ! x"$cross_compiling" = xyes; then

-		CPPFLAGS_FOR_BUILD=${CPPFLAGS}

-	fi

-fi

-AC_SUBST(CPPFLAGS_FOR_BUILD)

-

-if test x"$CFLAGS_FOR_BUILD" = x; then

-	if test ! x"$cross_compiling" = xyes; then

-		CFLAGS_FOR_BUILD=${CFLAGS}

-	fi

-fi

-AC_SUBST(CFLAGS_FOR_BUILD)

-

-if test x"$LDFLAGS_FOR_BUILD" = x; then

-	if test ! x"$cross_compiling" = xyes; then

-		LDFLAGS_FOR_BUILD=${LDFLAGS}

-	fi

-fi

-AC_SUBST(LDFLAGS_FOR_BUILD)

-

-# Find perl for "make check" tests in nls/Makefile.am

-AC_ARG_WITH(perl,

-	AC_HELP_STRING([--with-perl=<path>],

-			[path to perl interpreter for build-time tests]),

-	[PERL=$withval ; AC_MSG_CHECKING([perl]) ;

-	 AC_MSG_RESULT([(from --with-perl) $PERL])],

-	AC_CHECK_PROGS([PERL], [perl], [no]))

-AM_CONDITIONAL(HAVE_PERL, test x$PERL != xno)

-

-# Checks for pkg-config packages

-

-# Always required

-X11_REQUIRES='xproto >= 7.0.13 xextproto xtrans xcb >= 1.1.92'

-X11_EXTRA_DEPS="xcb >= 1.1.92"

-

-PKG_PROG_PKG_CONFIG()

-

-AC_SUBST(X11_EXTRA_DEPS)

-

-dnl Issue an error if xtrans.m4 was not found and XTRANS_CONNECTION_FLAGS macro

-dnl was not expanded, since libX11 with no transport types is rather useless.

-dnl

-dnl If you're seeing an error here, be sure you installed the lib/xtrans module

-dnl first and if it's not in the default location, that you set the ACLOCAL

-dnl environment variable to find it, such as:

-dnl	ACLOCAL="aclocal -I ${PREFIX}/share/aclocal"

-m4_pattern_forbid([^XTRANS_CONNECTION_FLAGS$])

-

-# Transport selection macro from xtrans.m4

-XTRANS_CONNECTION_FLAGS

-

-# Secure RPC detection macro from xtrans.m4

-XTRANS_SECURE_RPC_FLAGS

-

-# Preferred order to try transports for local connections

-AC_MSG_CHECKING([what order to try transports in for local connections])

-DEFAULT_LOCAL_TRANS=""

-case $host_os in

-	solaris*)

-		# On Solaris 2.6 through 9, named pipes (LOCAL_TRANS) were

-		# faster than Unix domain sockets, but on Solaris 10 & later,

-		# Unix domain sockets are faster now.

-		if test "$UNIXCONN" = "yes" ; then

-			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then

-				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"

-			fi

-			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}UNIX_TRANS"

-		fi

-		if test "$LOCALCONN" = "yes" ; then

-			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then

-				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"

-			fi

-			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}LOCAL_TRANS"

-		fi

-		if test "$TCPCONN" = "yes" ; then

-			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then

-				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"

-			fi

-			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}TCP_TRANS"

-		fi

-		;;

-	linux*)

-		# LOCAL_TRANS is used for abstract sockets.

-		if test "$UNIXCONN" = "yes" ; then

-			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then

-				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"

-			fi

-			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}LOCAL_TRANS,UNIX_TRANS"

-		fi

-		if test "$TCPCONN" = "yes" ; then

-			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then

-				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"

-			fi

-			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}TCP_TRANS"

-		fi

-		;;

-	*)

-		if test "$LOCALCONN" = "yes" ; then

-			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then

-				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"

-			fi

-			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}LOCAL_TRANS"

-		fi

-		if test "$UNIXCONN" = "yes" ; then

-			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then

-				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"

-			fi

-			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}UNIX_TRANS"

-		fi

-		if test "$TCPCONN" = "yes" ; then

-			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then

-				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"

-			fi

-			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}TCP_TRANS"

-		fi

-		;;

-esac

-

-AC_ARG_WITH(local-transport-order,

-	AC_HELP_STRING([--with-local-transport-order=LIST], [preference sorted list of transport types to try for local connections]),

-	[LOCAL_TRANSPORT_LIST=$withval],

-	[LOCAL_TRANSPORT_LIST=$DEFAULT_LOCAL_TRANS])

-AC_DEFINE_UNQUOTED([LOCAL_TRANSPORT_LIST], [$LOCAL_TRANSPORT_LIST],

-   [preference sorted list of transport types to try for local connections])

-AC_MSG_RESULT([$LOCAL_TRANSPORT_LIST])

-

-# Check for dlopen

-AC_MSG_CHECKING([if run-time linking is supported])

-AC_SEARCH_LIBS(dlopen,[dl svld])

-if test "x$ac_cv_search_dlopen" = xno; then

-	AC_SEARCH_LIBS(shl_load,[dld])

-	if test "x$ac_cv_search_shl_load" != xno; then

-		AC_DEFINE(HAVE_SHL_LOAD,1,

-			  [Use shl_load to load shared libraries])

-		AC_CHECK_HEADERS([dl.h])

-	fi

-else

-	AC_DEFINE(HAVE_DLOPEN,1,[Use dlopen to load shared libraries])

-	AC_CHECK_HEADERS([dlfcn.h])

-fi

-if test x$ac_cv_header_dlcfn_h -o x$ac_cv_header_dl_h; then

-	HAVE_LOADABLE_MODULES=yes

-else

-	HAVE_LOADABLE_MODULES=no

-fi

-AC_MSG_RESULT($HAVE_LOADABLE_MODULES)

-

-AC_MSG_CHECKING([if loadable i18n module support should be enabled])

-AC_ARG_ENABLE(loadable-i18n,

-	      AC_HELP_STRING([--enable-loadable-i18n],

-	       [Controls loadable i18n module support]),

-	       [XLIB_LOADABLE_I18N=$enableval],

-	       [XLIB_LOADABLE_I18N="no"])

-if test x$XLIB_LOADABLE_I18N = xyes; then

-	if test x$HAVE_LOADABLE_MODULES = xno; then

-		AC_MSG_ERROR([Loadable module support is required to enable loadable i18n module support])

-	fi

-	AC_DEFINE(USE_DYNAMIC_LC,1,

-		  [Split some i18n functions into loadable modules])

-	AC_SUBST(I18N_MODULE_LIBS,'${top_builddir}/src/libX11.la')

-fi

-AC_MSG_RESULT($XLIB_LOADABLE_I18N)

-

-AM_CONDITIONAL(XLIB_LOADABLE_I18N, test x$XLIB_LOADABLE_I18N = xyes)

-

-AC_MSG_CHECKING([if loadable Xcursor library support should be enabled])

-AC_ARG_ENABLE(loadable-xcursor,

-	      AC_HELP_STRING([--disable-loadable-xcursor],

-	       [Controls loadable xcursor library support]),

-	       [XLIB_LOADABLE_XCURSOR=$enableval],

-	       [XLIB_LOADABLE_XCURSOR=$HAVE_LOADABLE_MODULES])

-if test x$XLIB_LOADABLE_XCURSOR = xyes; then

-	AC_DEFINE(USE_DYNAMIC_XCURSOR,1,

-		  [Use the X cursor library to load cursors])

-fi

-AC_MSG_RESULT($XLIB_LOADABLE_XCURSOR)

-

-# Checks for header files.

-AC_HEADER_STDC

-AC_CHECK_HEADERS([sys/select.h])

-

-# Checks for typedefs, structures, and compiler characteristics.

-

-# Checks for library functions.

-AC_CHECK_FUNCS([strtol])

-# Used in lcFile.c (see also --enable-xlocaledir settings below)

-XLOCALEDIR_IS_SAFE="no"

-AC_CHECK_FUNC([issetugid], [XLOCALEDIR_IS_SAFE="yes"]

-	AC_DEFINE(HASSETUGID,1,[Has issetugid() function]))

-AC_CHECK_FUNC([getresuid], [XLOCALEDIR_IS_SAFE="yes"]

-	AC_DEFINE(HASGETRESUID,1,[Has getresuid() & getresgid() functions]))

-# Used in Font.c

-AC_CHECK_FUNC([shmat], AC_DEFINE(HAS_SHM,1,[Has shm*() functions]))

-

-# Checks for system services

-dnl AC_PATH_XTRA

-

-# arch specific things

-WCHAR32="1"

-case $host_os in

-  os2*) os2="true" ; WCHAR32="0" ;;

-  *) ;;

-esac

-AC_SUBST(WCHAR32)

-

-AM_CONDITIONAL(OS2, test x$os2 = xtrue)

-

-AC_ARG_WITH(launchd, AS_HELP_STRING([--with-launchd], [Build with support for Apple's launchd (default: auto)]), [LAUNCHD=$withval], [LAUNCHD=auto])

-if test "x$LAUNCHD" = xauto; then

-	unset LAUNCHD

-	AC_CHECK_PROG(LAUNCHD, [launchd], [yes], [no], [$PATH$PATH_SEPARATOR/sbin])

-fi

-

-if test "x$LAUNCHD" = xyes ; then

-	AC_DEFINE(HAVE_LAUNCHD, 1, [launchd support available])

-	AC_DEFINE(TRANS_REOPEN, 1, [launchd support available])

-fi

-

-AC_ARG_ENABLE(xthreads,

-              AC_HELP_STRING([--disable-xthreads],

-                [Disable Xlib support for Multithreading]),

-              [xthreads=$enableval],[xthreads=yes])

-

-AC_CHECK_LIB(c, getpwuid_r, [mtsafeapi="yes"], [mtsafeapi="no"])

-

-case x$xthreads in

-xyes)

-	AC_DEFINE(XTHREADS,1,[Whether libX11 is compiled with thread support])

-	if test x$mtsafeapi = xyes

-	then

-	AC_DEFINE(XUSE_MTSAFE_API,1,[Whether libX11 needs to use MT safe API's])

-	fi

-	;;

-*)

-	;;

-esac

-

-AC_CHECK_LIB(c, pthread_self, [thrstubs="no"], [thrstubs="yes"])

-AM_CONDITIONAL(THRSTUBS, test x$thrstubs = xyes)

-

-dnl XXX incomplete, please fill this in

-if test x$xthreads = xyes ; then

-    case $host_os in

-    linux*|openbsd*|gnu*|k*bsd*-gnu)

-        XTHREADLIB=-lpthread ;;

-    netbsd*)

-	XTHREAD_CFLAGS="-D_POSIX_THREAD_SAFE_FUNCTIONS"

-	XTHREADLIB="-lpthread" ;;

-    freebsd*)

-        XTHREAD_CFLAGS="-D_THREAD_SAFE"

-        XTHREADLIB="-pthread" ;;

-    dragonfly*)

-        XTHREADLIB="-pthread" ;;

-    solaris*)

-	XTHREAD_CFLAGS="-D_REENTRANT -D_POSIX_PTHREAD_SEMANTICS" ;;

-    esac

-fi

-AC_SUBST(XTHREADLIB)

-AC_SUBST(XTHREAD_CFLAGS)

-

-AC_CHECK_FUNC(poll, [AC_DEFINE(USE_POLL, 1, [poll() function is available])], )

-

-#

-# Find keysymdef.h

-#

-AC_MSG_CHECKING([keysym definitions])

-KEYSYMDEFDIR=`$PKG_CONFIG --variable=includedir xproto`/X11

-FILES="keysymdef.h XF86keysym.h Sunkeysym.h DECkeysym.h HPkeysym.h"

-for i in $FILES; do

-    if test -f "$KEYSYMDEFDIR/$i"; then

-            KEYSYMDEFS="$KEYSYMDEFS $KEYSYMDEFDIR/$i"

-    elif test "x$i" = "xkeysymdef.h"; then

-	    AC_MSG_ERROR([Cannot find keysymdef.h])

-    fi

-done

-AC_MSG_RESULT([$KEYSYMDEFS])

-AC_SUBST(KEYSYMDEFS)

-

-AM_CONDITIONAL(UDC, test xfalse = xtrue)

-

-AC_ARG_ENABLE(xcms,

-              AC_HELP_STRING([--disable-xcms],

-                [Disable Xlib support for CMS *EXPERIMENTAL*]),

-              [XCMS=$enableval],[XCMS=yes])

-AM_CONDITIONAL(XCMS, [test x$XCMS = xyes ])

-if test x"$XCMS" = "xyes"; then

-	AC_DEFINE(XCMS,1,[Include support for XCMS])

-fi

-

-AC_ARG_ENABLE(xlocale,

-              AC_HELP_STRING([--disable-xlocale],

-                [Disable Xlib locale implementation *EXPERIMENTAL*]),

-              [XLOCALE=$enableval],[XLOCALE=yes])

-

-AM_CONDITIONAL(XLOCALE, [ test x$XLOCALE = xyes ])

-if test x"$XLOCALE" = "xyes"; then

-	AC_DEFINE(XLOCALE,1,[support for X Locales])

-fi

-

-# This disables XLOCALEDIR.  Set it if you're using BuildLoadableXlibI18n,

-# don't have either issetugid() or getresuid(), and you need to protect

-# clients that are setgid or setuid to an id other than 0.

-AC_MSG_CHECKING([if XLOCALEDIR support should be enabled])

-AC_ARG_ENABLE(xlocaledir,

-	      AC_HELP_STRING([--enable-xlocaledir],

-		[Enable XLOCALEDIR environment variable support]),

-	      [ENABLE_XLOCALEDIR=$enableval],[ENABLE_XLOCALEDIR=$XLOCALEDIR_IS_SAFE])

-if test "x$ENABLE_XLOCALEDIR" = "xno"; then

-	AC_DEFINE(NO_XLOCALEDIR,1,[Disable XLOCALEDIR environment variable])

-fi

-AC_MSG_RESULT($ENABLE_XLOCALEDIR)

-

-AC_ARG_ENABLE(xf86bigfont,

-	      AC_HELP_STRING([--disable-xf86bigfont],

-		[Disable XF86BigFont extension support]),

-	      [XF86BIGFONT=$enableval],[XF86BIGFONT="yes"])

-if test "x$XF86BIGFONT" = "xyes"; then

-    PKG_CHECK_MODULES(BIGFONT, xf86bigfontproto,

-         AC_DEFINE(XF86BIGFONT,1,[Enable XF86BIGFONT extension]),XF86BIGFONT="no")

-    AC_SUBST(BIGFONT_CFLAGS)

-    AC_SUBST(BIGFONT_LIBS)

-fi

-

-AC_ARG_ENABLE(xkb,

-              AC_HELP_STRING([--disable-xkb],

-                [Disable XKB support *EXPERIMENTAL*]),

-              [XKB=$enableval],[XKB=yes])

-

-AM_CONDITIONAL(XKB, [ test x$XKB = xyes ])

-if test x"$XKB" = "xyes"; then

-   XKBPROTO_REQUIRES="kbproto"

-   X11_REQUIRES="${X11_REQUIRES} kbproto inputproto"

-   AC_DEFINE(XKB,1,[Use XKB])

-else

-   XKBPROTO_REQUIRES=""

-fi

-AC_SUBST(XKBPROTO_REQUIRES)

-

-AC_FUNC_MMAP()

-composecache_default=$ac_cv_func_mmap_fixed_mapped

-AC_CHECK_FUNC(nl_langinfo, , [composecache_default=no])

-AC_ARG_ENABLE(composecache,

-              AC_HELP_STRING([--disable-composecache],

-                [Disable compose table cache support]),

-              [COMPOSECACHE=$enableval],[COMPOSECACHE=$composecache_default])

-if test x"$COMPOSECACHE" = "xyes"; then

-	AC_DEFINE(COMPOSECACHE,1,[Include compose table cache support])

-fi

-

-dnl Allow checking code with lint, sparse, etc.

-XORG_WITH_LINT

-XORG_LINT_LIBRARY([X11])

-

-X11_DATADIR="${datadir}/X11"

-AX_DEFINE_DIR(X11_DATADIR, X11_DATADIR, [Location of libX11 data])

-AC_SUBST(X11_DATADIR)

-

-X11_LIBDIR="${libdir}/X11"

-AX_DEFINE_DIR(X11_LIBDIR, X11_LIBDIR, [Location of libX11 library data])

-AC_SUBST(X11_LIBDIR)

-

-PKG_CHECK_MODULES(X11, [$X11_REQUIRES])

-X11_CFLAGS="$X11_CFLAGS $XTHREAD_CFLAGS"

-

-#

-# Yes, it would be nice to put the locale data in

-# /usr/share, but the locale stuff includes loadable

-# libraries which must be located in the same directory

-# as the other locale data, so for now, everything lives

-# in ${libdir}

-#

-

-X11_LOCALEDATADIR="${X11_DATADIR}/locale"

-AX_DEFINE_DIR(XLOCALEDATADIR, X11_LOCALEDATADIR, [Location of libX11 locale data])

-AC_SUBST(X11_LOCALEDATADIR)

-

-AC_ARG_WITH(locale-lib-dir,	AS_HELP_STRING([--with-locale-lib-dir=DIR],

- [Directory where locale libraries files are installed (default: $libdir/X11/locale)]),

-				[ X11_LOCALELIBDIR="$withval" ],

-				[ X11_LOCALELIBDIR="${X11_LIBDIR}/locale" ])

-AX_DEFINE_DIR(XLOCALELIBDIR, X11_LOCALELIBDIR, [Location of libX11 locale libraries])

-AC_SUBST(X11_LOCALELIBDIR)

-

-X11_LOCALEDIR="${X11_LOCALEDATADIR}"

-AX_DEFINE_DIR(XLOCALEDIR, X11_LOCALEDIR, [Location of libX11 locale data])

-AC_SUBST(X11_LOCALEDIR)

-

-XKEYSYMDB="${X11_DATADIR}/XKeysymDB"

-AX_DEFINE_DIR(XKEYSYMDB, XKEYSYMDB, [Location of keysym database])

-

-XERRORDB="${X11_DATADIR}/XErrorDB"

-AX_DEFINE_DIR(XERRORDB, XERRORDB, [Location of error message database])

-

-XORG_CHECK_MALLOC_ZERO

-

-AC_OUTPUT([Makefile

-           include/Makefile

-	   man/Makefile

-           man/xkb/Makefile

-           src/Makefile

-           src/util/Makefile

-	   src/xcms/Makefile

-	   src/xlibi18n/Makefile

-	   modules/Makefile

-	   modules/im/Makefile

-	   modules/im/ximcp/Makefile

-	   modules/lc/Makefile

-	   modules/lc/def/Makefile

-	   modules/lc/gen/Makefile

-	   modules/lc/Utf8/Makefile

-	   modules/lc/xlocale/Makefile

-	   modules/om/Makefile

-	   modules/om/generic/Makefile

-	   src/xkb/Makefile

-	   nls/Makefile

-	   specs/Makefile

-	   specs/i18n/Makefile

-	   specs/i18n/framework/Makefile

-	   specs/i18n/localedb/Makefile

-	   specs/i18n/trans/Makefile

-	   specs/libX11/Makefile

-	   specs/XIM/Makefile

-	   specs/XKB/Makefile

-	   x11.pc

-	   x11-xcb.pc])

-

-echo ""

-echo "X11 will be built with the following settings:"

-echo " Loadable i18n module support:            "$XLIB_LOADABLE_I18N

-echo " Loadable xcursor library support:        "$XLIB_LOADABLE_XCURSOR

-echo " Threading support:                       "$xthreads

-echo " Use Threads safe API:                    "$mtsafeapi

-echo " Threads stubs in libX11:                 "$thrstubs

-echo " XCMS:                                    "$XCMS

-echo " Internationalization support:            "$XLOCALE

-echo " XF86BigFont support:                     "$XF86BIGFONT

-echo " XKB support:                             "$XKB

-echo " XLOCALEDIR environment variable support: "$ENABLE_XLOCALEDIR

-echo " Compose table cache enabled:             "$COMPOSECACHE

-echo " Functional specs building enabled:       "$build_specs

-echo ""

+#                                               -*- Autoconf -*-
+# Process this file with autoconf to produce a configure script.
+
+AC_PREREQ(2.60)
+AC_INIT([libX11],
+        [1.4.1],
+        [https://bugs.freedesktop.org/enter_bug.cgi?product=xorg],
+        libX11)
+AC_CONFIG_SRCDIR([Makefile.am])
+AC_CONFIG_HEADERS([src/config.h include/X11/XlibConf.h])
+AC_CONFIG_MACRO_DIR([m4])
+AC_CANONICAL_BUILD
+AC_CANONICAL_HOST
+
+AM_INIT_AUTOMAKE([foreign dist-bzip2])
+AM_MAINTAINER_MODE
+
+# Set common system defines for POSIX extensions, such as _GNU_SOURCE
+# Must be called before any macros that run the compiler (like AC_PROG_LIBTOOL)
+# to avoid autoconf errors.
+AC_USE_SYSTEM_EXTENSIONS
+
+# Require xorg-macros minimum of 1.11 for disabling fop by default
+m4_ifndef([XORG_MACROS_VERSION],
+          [m4_fatal([must install xorg-macros 1.11 or later before running autoconf/autogen])])
+XORG_MACROS_VERSION(1.11)
+XORG_DEFAULT_OPTIONS
+XORG_ENABLE_SPECS
+XORG_WITH_XMLTO(0.0.20)
+XORG_WITH_FOP([no])
+XORG_CHECK_SGML_DOCTOOLS(1.5)
+XORG_PROG_RAWCPP
+
+# Checks for programs.
+AC_PROG_LIBTOOL
+PKG_PROG_PKG_CONFIG
+
+if test x"$CC_FOR_BUILD" = x; then
+	if test x"$cross_compiling" = xyes; then
+	       AC_CHECK_PROGS(CC_FOR_BUILD, gcc cc)
+	else
+	       CC_FOR_BUILD="$CC"
+	fi
+fi
+AC_SUBST([CC_FOR_BUILD])
+
+if test x"$CPPFLAGS_FOR_BUILD" = x; then
+	if test ! x"$cross_compiling" = xyes; then
+		CPPFLAGS_FOR_BUILD=${CPPFLAGS}
+	fi
+fi
+AC_SUBST(CPPFLAGS_FOR_BUILD)
+
+if test x"$CFLAGS_FOR_BUILD" = x; then
+	if test ! x"$cross_compiling" = xyes; then
+		CFLAGS_FOR_BUILD=${CFLAGS}
+	fi
+fi
+AC_SUBST(CFLAGS_FOR_BUILD)
+
+if test x"$LDFLAGS_FOR_BUILD" = x; then
+	if test ! x"$cross_compiling" = xyes; then
+		LDFLAGS_FOR_BUILD=${LDFLAGS}
+	fi
+fi
+AC_SUBST(LDFLAGS_FOR_BUILD)
+
+# Find perl for "make check" tests in nls/Makefile.am
+AC_ARG_WITH(perl,
+	AC_HELP_STRING([--with-perl=<path>],
+			[path to perl interpreter for build-time tests]),
+	[PERL=$withval ; AC_MSG_CHECKING([perl]) ;
+	 AC_MSG_RESULT([(from --with-perl) $PERL])],
+	AC_CHECK_PROGS([PERL], [perl], [no]))
+AM_CONDITIONAL(HAVE_PERL, test x$PERL != xno)
+
+# Checks for pkg-config packages
+
+# Always required
+X11_REQUIRES='xproto >= 7.0.13 xextproto xtrans xcb >= 1.1.92'
+X11_EXTRA_DEPS="xcb >= 1.1.92"
+
+PKG_PROG_PKG_CONFIG()
+
+AC_SUBST(X11_EXTRA_DEPS)
+
+dnl Issue an error if xtrans.m4 was not found and XTRANS_CONNECTION_FLAGS macro
+dnl was not expanded, since libX11 with no transport types is rather useless.
+dnl
+dnl If you're seeing an error here, be sure you installed the lib/xtrans module
+dnl first and if it's not in the default location, that you set the ACLOCAL
+dnl environment variable to find it, such as:
+dnl	ACLOCAL="aclocal -I ${PREFIX}/share/aclocal"
+m4_pattern_forbid([^XTRANS_CONNECTION_FLAGS$])
+
+# Transport selection macro from xtrans.m4
+XTRANS_CONNECTION_FLAGS
+
+# Secure RPC detection macro from xtrans.m4
+XTRANS_SECURE_RPC_FLAGS
+
+# Preferred order to try transports for local connections
+AC_MSG_CHECKING([what order to try transports in for local connections])
+DEFAULT_LOCAL_TRANS=""
+case $host_os in
+	solaris*)
+		# On Solaris 2.6 through 9, named pipes (LOCAL_TRANS) were
+		# faster than Unix domain sockets, but on Solaris 10 & later,
+		# Unix domain sockets are faster now.
+		if test "$UNIXCONN" = "yes" ; then
+			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then
+				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"
+			fi
+			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}UNIX_TRANS"
+		fi
+		if test "$LOCALCONN" = "yes" ; then
+			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then
+				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"
+			fi
+			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}LOCAL_TRANS"
+		fi
+		if test "$TCPCONN" = "yes" ; then
+			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then
+				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"
+			fi
+			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}TCP_TRANS"
+		fi
+		;;
+	linux*)
+		# LOCAL_TRANS is used for abstract sockets.
+		if test "$UNIXCONN" = "yes" ; then
+			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then
+				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"
+			fi
+			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}LOCAL_TRANS,UNIX_TRANS"
+		fi
+		if test "$TCPCONN" = "yes" ; then
+			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then
+				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"
+			fi
+			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}TCP_TRANS"
+		fi
+		;;
+	*)
+		if test "$LOCALCONN" = "yes" ; then
+			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then
+				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"
+			fi
+			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}LOCAL_TRANS"
+		fi
+		if test "$UNIXCONN" = "yes" ; then
+			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then
+				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"
+			fi
+			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}UNIX_TRANS"
+		fi
+		if test "$TCPCONN" = "yes" ; then
+			if test ! "x$DEFAULT_LOCAL_TRANS" = "x" ; then
+				DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS},"
+			fi
+			DEFAULT_LOCAL_TRANS="${DEFAULT_LOCAL_TRANS}TCP_TRANS"
+		fi
+		;;
+esac
+
+AC_ARG_WITH(local-transport-order,
+	AC_HELP_STRING([--with-local-transport-order=LIST], [preference sorted list of transport types to try for local connections]),
+	[LOCAL_TRANSPORT_LIST=$withval],
+	[LOCAL_TRANSPORT_LIST=$DEFAULT_LOCAL_TRANS])
+AC_DEFINE_UNQUOTED([LOCAL_TRANSPORT_LIST], [$LOCAL_TRANSPORT_LIST],
+   [preference sorted list of transport types to try for local connections])
+AC_MSG_RESULT([$LOCAL_TRANSPORT_LIST])
+
+# Check for dlopen
+AC_MSG_CHECKING([if run-time linking is supported])
+AC_SEARCH_LIBS(dlopen,[dl svld])
+if test "x$ac_cv_search_dlopen" = xno; then
+	AC_SEARCH_LIBS(shl_load,[dld])
+	if test "x$ac_cv_search_shl_load" != xno; then
+		AC_DEFINE(HAVE_SHL_LOAD,1,
+			  [Use shl_load to load shared libraries])
+		AC_CHECK_HEADERS([dl.h])
+	fi
+else
+	AC_DEFINE(HAVE_DLOPEN,1,[Use dlopen to load shared libraries])
+	AC_CHECK_HEADERS([dlfcn.h])
+fi
+if test x$ac_cv_header_dlcfn_h -o x$ac_cv_header_dl_h; then
+	HAVE_LOADABLE_MODULES=yes
+else
+	HAVE_LOADABLE_MODULES=no
+fi
+AC_MSG_RESULT($HAVE_LOADABLE_MODULES)
+
+AC_MSG_CHECKING([if loadable i18n module support should be enabled])
+AC_ARG_ENABLE(loadable-i18n,
+	      AC_HELP_STRING([--enable-loadable-i18n],
+	       [Controls loadable i18n module support]),
+	       [XLIB_LOADABLE_I18N=$enableval],
+	       [XLIB_LOADABLE_I18N="no"])
+if test x$XLIB_LOADABLE_I18N = xyes; then
+	if test x$HAVE_LOADABLE_MODULES = xno; then
+		AC_MSG_ERROR([Loadable module support is required to enable loadable i18n module support])
+	fi
+	AC_DEFINE(USE_DYNAMIC_LC,1,
+		  [Split some i18n functions into loadable modules])
+	AC_SUBST(I18N_MODULE_LIBS,'${top_builddir}/src/libX11.la')
+fi
+AC_MSG_RESULT($XLIB_LOADABLE_I18N)
+
+AM_CONDITIONAL(XLIB_LOADABLE_I18N, test x$XLIB_LOADABLE_I18N = xyes)
+
+AC_MSG_CHECKING([if loadable Xcursor library support should be enabled])
+AC_ARG_ENABLE(loadable-xcursor,
+	      AC_HELP_STRING([--disable-loadable-xcursor],
+	       [Controls loadable xcursor library support]),
+	       [XLIB_LOADABLE_XCURSOR=$enableval],
+	       [XLIB_LOADABLE_XCURSOR=$HAVE_LOADABLE_MODULES])
+if test x$XLIB_LOADABLE_XCURSOR = xyes; then
+	AC_DEFINE(USE_DYNAMIC_XCURSOR,1,
+		  [Use the X cursor library to load cursors])
+fi
+AC_MSG_RESULT($XLIB_LOADABLE_XCURSOR)
+
+# Checks for header files.
+AC_HEADER_STDC
+AC_CHECK_HEADERS([sys/select.h])
+
+# Checks for typedefs, structures, and compiler characteristics.
+
+# Checks for library functions.
+AC_CHECK_FUNCS([strtol])
+# Used in lcFile.c (see also --enable-xlocaledir settings below)
+XLOCALEDIR_IS_SAFE="no"
+AC_CHECK_FUNC([issetugid], [XLOCALEDIR_IS_SAFE="yes"]
+	AC_DEFINE(HASSETUGID,1,[Has issetugid() function]))
+AC_CHECK_FUNC([getresuid], [XLOCALEDIR_IS_SAFE="yes"]
+	AC_DEFINE(HASGETRESUID,1,[Has getresuid() & getresgid() functions]))
+# Used in Font.c
+AC_CHECK_FUNC([shmat], AC_DEFINE(HAS_SHM,1,[Has shm*() functions]))
+
+# Checks for system services
+dnl AC_PATH_XTRA
+
+# arch specific things
+WCHAR32="1"
+case $host_os in
+  os2*) os2="true" ; WCHAR32="0" ;;
+  *) ;;
+esac
+AC_SUBST(WCHAR32)
+
+AM_CONDITIONAL(OS2, test x$os2 = xtrue)
+
+AC_ARG_WITH(launchd, AS_HELP_STRING([--with-launchd], [Build with support for Apple's launchd (default: auto)]), [LAUNCHD=$withval], [LAUNCHD=auto])
+if test "x$LAUNCHD" = xauto; then
+	unset LAUNCHD
+	AC_CHECK_PROG(LAUNCHD, [launchd], [yes], [no], [$PATH$PATH_SEPARATOR/sbin])
+fi
+
+if test "x$LAUNCHD" = xyes ; then
+	AC_DEFINE(HAVE_LAUNCHD, 1, [launchd support available])
+	AC_DEFINE(TRANS_REOPEN, 1, [launchd support available])
+fi
+
+AC_ARG_ENABLE(xthreads,
+              AC_HELP_STRING([--disable-xthreads],
+                [Disable Xlib support for Multithreading]),
+              [xthreads=$enableval],[xthreads=yes])
+
+AC_CHECK_LIB(c, getpwuid_r, [mtsafeapi="yes"], [mtsafeapi="no"])
+
+case x$xthreads in
+xyes)
+	AC_DEFINE(XTHREADS,1,[Whether libX11 is compiled with thread support])
+	if test x$mtsafeapi = xyes
+	then
+	AC_DEFINE(XUSE_MTSAFE_API,1,[Whether libX11 needs to use MT safe API's])
+	fi
+	;;
+*)
+	;;
+esac
+
+AC_CHECK_LIB(c, pthread_self, [thrstubs="no"], [thrstubs="yes"])
+AM_CONDITIONAL(THRSTUBS, test x$thrstubs = xyes)
+
+dnl XXX incomplete, please fill this in
+if test x$xthreads = xyes ; then
+    case $host_os in
+    linux*|openbsd*|gnu*|k*bsd*-gnu)
+        XTHREADLIB=-lpthread ;;
+    netbsd*)
+	XTHREAD_CFLAGS="-D_POSIX_THREAD_SAFE_FUNCTIONS"
+	XTHREADLIB="-lpthread" ;;
+    freebsd*)
+        XTHREAD_CFLAGS="-D_THREAD_SAFE"
+        XTHREADLIB="-pthread" ;;
+    dragonfly*)
+        XTHREADLIB="-pthread" ;;
+    solaris*)
+	XTHREAD_CFLAGS="-D_REENTRANT -D_POSIX_PTHREAD_SEMANTICS" ;;
+    esac
+fi
+AC_SUBST(XTHREADLIB)
+AC_SUBST(XTHREAD_CFLAGS)
+
+AC_CHECK_FUNC(poll, [AC_DEFINE(USE_POLL, 1, [poll() function is available])], )
+
+#
+# Find keysymdef.h
+#
+AC_MSG_CHECKING([keysym definitions])
+KEYSYMDEFDIR=`$PKG_CONFIG --variable=includedir xproto`/X11
+FILES="keysymdef.h XF86keysym.h Sunkeysym.h DECkeysym.h HPkeysym.h"
+for i in $FILES; do
+    if test -f "$KEYSYMDEFDIR/$i"; then
+            KEYSYMDEFS="$KEYSYMDEFS $KEYSYMDEFDIR/$i"
+    elif test "x$i" = "xkeysymdef.h"; then
+	    AC_MSG_ERROR([Cannot find keysymdef.h])
+    fi
+done
+AC_MSG_RESULT([$KEYSYMDEFS])
+AC_SUBST(KEYSYMDEFS)
+
+AM_CONDITIONAL(UDC, test xfalse = xtrue)
+
+AC_ARG_ENABLE(xcms,
+              AC_HELP_STRING([--disable-xcms],
+                [Disable Xlib support for CMS *EXPERIMENTAL*]),
+              [XCMS=$enableval],[XCMS=yes])
+AM_CONDITIONAL(XCMS, [test x$XCMS = xyes ])
+if test x"$XCMS" = "xyes"; then
+	AC_DEFINE(XCMS,1,[Include support for XCMS])
+fi
+
+AC_ARG_ENABLE(xlocale,
+              AC_HELP_STRING([--disable-xlocale],
+                [Disable Xlib locale implementation *EXPERIMENTAL*]),
+              [XLOCALE=$enableval],[XLOCALE=yes])
+
+AM_CONDITIONAL(XLOCALE, [ test x$XLOCALE = xyes ])
+if test x"$XLOCALE" = "xyes"; then
+	AC_DEFINE(XLOCALE,1,[support for X Locales])
+fi
+
+# This disables XLOCALEDIR.  Set it if you're using BuildLoadableXlibI18n,
+# don't have either issetugid() or getresuid(), and you need to protect
+# clients that are setgid or setuid to an id other than 0.
+AC_MSG_CHECKING([if XLOCALEDIR support should be enabled])
+AC_ARG_ENABLE(xlocaledir,
+	      AC_HELP_STRING([--enable-xlocaledir],
+		[Enable XLOCALEDIR environment variable support]),
+	      [ENABLE_XLOCALEDIR=$enableval],[ENABLE_XLOCALEDIR=$XLOCALEDIR_IS_SAFE])
+if test "x$ENABLE_XLOCALEDIR" = "xno"; then
+	AC_DEFINE(NO_XLOCALEDIR,1,[Disable XLOCALEDIR environment variable])
+fi
+AC_MSG_RESULT($ENABLE_XLOCALEDIR)
+
+AC_ARG_ENABLE(xf86bigfont,
+	      AC_HELP_STRING([--disable-xf86bigfont],
+		[Disable XF86BigFont extension support]),
+	      [XF86BIGFONT=$enableval],[XF86BIGFONT="yes"])
+if test "x$XF86BIGFONT" = "xyes"; then
+    PKG_CHECK_MODULES(BIGFONT, [xf86bigfontproto >= 1.2.0],
+         AC_DEFINE(XF86BIGFONT,1,[Enable XF86BIGFONT extension]),XF86BIGFONT="no")
+fi
+
+AC_ARG_ENABLE(xkb,
+              AC_HELP_STRING([--disable-xkb],
+                [Disable XKB support *EXPERIMENTAL*]),
+              [XKB=$enableval],[XKB=yes])
+
+AM_CONDITIONAL(XKB, [ test x$XKB = xyes ])
+if test x"$XKB" = "xyes"; then
+   XKBPROTO_REQUIRES="kbproto"
+   X11_REQUIRES="${X11_REQUIRES} kbproto inputproto"
+   AC_DEFINE(XKB,1,[Use XKB])
+else
+   XKBPROTO_REQUIRES=""
+fi
+AC_SUBST(XKBPROTO_REQUIRES)
+
+AC_FUNC_MMAP()
+composecache_default=$ac_cv_func_mmap_fixed_mapped
+AC_CHECK_FUNC(nl_langinfo, , [composecache_default=no])
+AC_ARG_ENABLE(composecache,
+              AC_HELP_STRING([--disable-composecache],
+                [Disable compose table cache support]),
+              [COMPOSECACHE=$enableval],[COMPOSECACHE=$composecache_default])
+if test x"$COMPOSECACHE" = "xyes"; then
+	AC_DEFINE(COMPOSECACHE,1,[Include compose table cache support])
+fi
+
+dnl Allow checking code with lint, sparse, etc.
+XORG_WITH_LINT
+XORG_LINT_LIBRARY([X11])
+
+X11_DATADIR="${datadir}/X11"
+AX_DEFINE_DIR(X11_DATADIR, X11_DATADIR, [Location of libX11 data])
+AC_SUBST(X11_DATADIR)
+
+X11_LIBDIR="${libdir}/X11"
+AX_DEFINE_DIR(X11_LIBDIR, X11_LIBDIR, [Location of libX11 library data])
+AC_SUBST(X11_LIBDIR)
+
+PKG_CHECK_MODULES(X11, [$X11_REQUIRES])
+X11_CFLAGS="$X11_CFLAGS $XTHREAD_CFLAGS"
+
+#
+# Yes, it would be nice to put the locale data in
+# /usr/share, but the locale stuff includes loadable
+# libraries which must be located in the same directory
+# as the other locale data, so for now, everything lives
+# in ${libdir}
+#
+
+X11_LOCALEDATADIR="${X11_DATADIR}/locale"
+AX_DEFINE_DIR(XLOCALEDATADIR, X11_LOCALEDATADIR, [Location of libX11 locale data])
+AC_SUBST(X11_LOCALEDATADIR)
+
+AC_ARG_WITH(locale-lib-dir,	AS_HELP_STRING([--with-locale-lib-dir=DIR],
+ [Directory where locale libraries files are installed (default: $libdir/X11/locale)]),
+				[ X11_LOCALELIBDIR="$withval" ],
+				[ X11_LOCALELIBDIR="${X11_LIBDIR}/locale" ])
+AX_DEFINE_DIR(XLOCALELIBDIR, X11_LOCALELIBDIR, [Location of libX11 locale libraries])
+AC_SUBST(X11_LOCALELIBDIR)
+
+X11_LOCALEDIR="${X11_LOCALEDATADIR}"
+AX_DEFINE_DIR(XLOCALEDIR, X11_LOCALEDIR, [Location of libX11 locale data])
+AC_SUBST(X11_LOCALEDIR)
+
+XKEYSYMDB="${X11_DATADIR}/XKeysymDB"
+AX_DEFINE_DIR(XKEYSYMDB, XKEYSYMDB, [Location of keysym database])
+
+XERRORDB="${X11_DATADIR}/XErrorDB"
+AX_DEFINE_DIR(XERRORDB, XERRORDB, [Location of error message database])
+
+XORG_CHECK_MALLOC_ZERO
+
+AC_OUTPUT([Makefile
+           include/Makefile
+	   man/Makefile
+           man/xkb/Makefile
+           src/Makefile
+           src/util/Makefile
+	   src/xcms/Makefile
+	   src/xlibi18n/Makefile
+	   modules/Makefile
+	   modules/im/Makefile
+	   modules/im/ximcp/Makefile
+	   modules/lc/Makefile
+	   modules/lc/def/Makefile
+	   modules/lc/gen/Makefile
+	   modules/lc/Utf8/Makefile
+	   modules/lc/xlocale/Makefile
+	   modules/om/Makefile
+	   modules/om/generic/Makefile
+	   src/xkb/Makefile
+	   nls/Makefile
+	   specs/Makefile
+	   specs/i18n/Makefile
+	   specs/i18n/framework/Makefile
+	   specs/i18n/localedb/Makefile
+	   specs/i18n/trans/Makefile
+	   specs/libX11/Makefile
+	   specs/XIM/Makefile
+	   specs/XKB/Makefile
+	   x11.pc
+	   x11-xcb.pc])
+
+echo ""
+echo "X11 will be built with the following settings:"
+echo " Loadable i18n module support:            "$XLIB_LOADABLE_I18N
+echo " Loadable xcursor library support:        "$XLIB_LOADABLE_XCURSOR
+echo " Threading support:                       "$xthreads
+echo " Use Threads safe API:                    "$mtsafeapi
+echo " Threads stubs in libX11:                 "$thrstubs
+echo " XCMS:                                    "$XCMS
+echo " Internationalization support:            "$XLOCALE
+echo " XF86BigFont support:                     "$XF86BIGFONT
+echo " XKB support:                             "$XKB
+echo " XLOCALEDIR environment variable support: "$ENABLE_XLOCALEDIR
+echo " Compose table cache enabled:             "$COMPOSECACHE
+echo " Functional specs building enabled:       "$build_specs
+echo ""
diff --git a/libX11/src/Font.c b/libX11/src/Font.c
index 857136a34..7f56f686b 100644
--- a/libX11/src/Font.c
+++ b/libX11/src/Font.c
@@ -1,730 +1,730 @@
-/*

-

-Copyright 1986, 1998  The Open Group

-Copyright (c) 2000  The XFree86 Project, Inc.

-

-Permission to use, copy, modify, distribute, and sell this software and its

-documentation for any purpose is hereby granted without fee, provided that

-the above copyright notice appear in all copies and that both that

-copyright notice and this permission notice appear in supporting

-documentation.

-

-The above copyright notice and this permission notice shall be included in

-all copies or substantial portions of the Software.

-

-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE

-X CONSORTIUM OR THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

-SOFTWARE.

-

-Except as contained in this notice, the name of the X Consortium or of the

-XFree86 Project shall not be used in advertising or otherwise to promote the

-sale, use or other dealings in this Software without prior written

-authorization from the X Consortium and the XFree86 Project.

-

-*/

-

-#ifdef HAVE_CONFIG_H

-#include <config.h>

-#endif

-#include "Xlibint.h"

-

-#if defined(XF86BIGFONT) && !defined(MUSTCOPY)

-#define USE_XF86BIGFONT

-#endif

-#ifdef USE_XF86BIGFONT

-#include <sys/types.h>

-#ifdef HAS_SHM

-#include <sys/ipc.h>

-#include <sys/shm.h>

-#endif

-

-#include <stdio.h>

-#include <stdlib.h>

-#include <X11/extensions/xf86bigfstr.h>

-#endif

-

-#include "Xlcint.h"

-#include "XlcPubI.h"

-

-

-static XFontStruct *_XQueryFont(

-    Display*		/* dpy */,

-    Font		/* fid */,

-    unsigned long	/* seq */

-);

-

-#ifdef USE_XF86BIGFONT

-

-/* Private data for this extension. */

-typedef struct {

-    XExtCodes *codes;

-    CARD32 serverSignature;

-    CARD32 serverCapabilities;

-} XF86BigfontCodes;

-

-/* Additional bit masks that can be set in serverCapabilities */

-#define CAP_VerifiedLocal 256

-

-static XF86BigfontCodes *_XF86BigfontCodes(

-    Display*		/* dpy */

-);

-

-static XFontStruct *_XF86BigfontQueryFont(

-    Display*		/* dpy */,

-    XF86BigfontCodes*	/* extcodes */,

-    Font		/* fid */,

-    unsigned long	/* seq */

-);

-

-void _XF86BigfontFreeFontMetrics(

-    XFontStruct*	/* fs */

-);

-

-#endif /* USE_XF86BIGFONT */

-

-

-XFontStruct *XLoadQueryFont(

-   register Display *dpy,

-   _Xconst char *name)

-{

-    XFontStruct *font_result;

-    register long nbytes;

-    Font fid;

-    xOpenFontReq *req;

-    unsigned long seq;

-#ifdef USE_XF86BIGFONT

-    XF86BigfontCodes *extcodes = _XF86BigfontCodes(dpy);

-#endif

-

-    if (_XF86LoadQueryLocaleFont(dpy, name, &font_result, (Font *)0))

-      return font_result;

-    LockDisplay(dpy);

-    GetReq(OpenFont, req);

-    seq = dpy->request;

-    nbytes = req->nbytes  = name ? strlen(name) : 0;

-    req->fid = fid = XAllocID(dpy);

-    req->length += (nbytes+3)>>2;

-    Data (dpy, name, nbytes);

-    font_result = NULL;

-#ifdef USE_XF86BIGFONT

-    if (extcodes) {

-	font_result = _XF86BigfontQueryFont(dpy, extcodes, fid, seq);

-	seq = 0;

-    }

-#endif

-    if (!font_result)

-	font_result = _XQueryFont(dpy, fid, seq);

-    UnlockDisplay(dpy);

-    SyncHandle();

-    return font_result;

-}

-

-XFontStruct *XQueryFont (

-    register Display *dpy,

-    Font fid)

-{

-    XFontStruct *font_result;

-#ifdef USE_XF86BIGFONT

-    XF86BigfontCodes *extcodes = _XF86BigfontCodes(dpy);

-#endif

-

-    LockDisplay(dpy);

-    font_result = NULL;

-#ifdef USE_XF86BIGFONT

-    if (extcodes) {

-	font_result = _XF86BigfontQueryFont(dpy, extcodes, fid, 0L);

-    }

-#endif

-    if (!font_result)

-	font_result = _XQueryFont(dpy, fid, 0L);

-    UnlockDisplay(dpy);

-    SyncHandle();

-    return font_result;

-}

-

-int

-XFreeFont(

-    register Display *dpy,

-    XFontStruct *fs)

-{

-    register xResourceReq *req;

-    register _XExtension *ext;

-

-    LockDisplay(dpy);

-    /* call out to any extensions interested */

-    for (ext = dpy->ext_procs; ext; ext = ext->next)

-	if (ext->free_Font) (*ext->free_Font)(dpy, fs, &ext->codes);

-    GetResReq (CloseFont, fs->fid, req);

-    UnlockDisplay(dpy);

-    SyncHandle();

-    if (fs->per_char) {

-#ifdef USE_XF86BIGFONT

-	_XF86BigfontFreeFontMetrics(fs);

-#else

-	Xfree ((char *) fs->per_char);

-#endif

-    }

-    _XFreeExtData(fs->ext_data);

-    if (fs->properties)

-	Xfree ((char *) fs->properties);

-    Xfree ((char *) fs);

-    return 1;

-}

-

-

-static XFontStruct *

-_XQueryFont (

-    register Display *dpy,

-    Font fid,

-    unsigned long seq)

-{

-    register XFontStruct *fs;

-    register long nbytes;

-    xQueryFontReply reply;

-    register xResourceReq *req;

-    register _XExtension *ext;

-    _XAsyncHandler async;

-    _XAsyncErrorState async_state;

-

-    if (seq) {

-	async_state.min_sequence_number = seq;

-	async_state.max_sequence_number = seq;

-	async_state.error_code = BadName;

-	async_state.major_opcode = X_OpenFont;

-	async_state.minor_opcode = 0;

-	async_state.error_count = 0;

-	async.next = dpy->async_handlers;

-	async.handler = _XAsyncErrorHandler;

-	async.data = (XPointer)&async_state;

-	dpy->async_handlers = &async;

-    }

-    GetResReq(QueryFont, fid, req);

-    if (!_XReply (dpy, (xReply *) &reply,

-       ((SIZEOF(xQueryFontReply) - SIZEOF(xReply)) >> 2), xFalse)) {

-	if (seq)

-	    DeqAsyncHandler(dpy, &async);

-	return (XFontStruct *)NULL;

-    }

-    if (seq)

-	DeqAsyncHandler(dpy, &async);

-    if (! (fs = (XFontStruct *) Xmalloc (sizeof (XFontStruct)))) {

-	_XEatData(dpy, (unsigned long)(reply.nFontProps * SIZEOF(xFontProp) +

-				       reply.nCharInfos * SIZEOF(xCharInfo)));

-	return (XFontStruct *)NULL;

-    }

-    fs->ext_data 		= NULL;

-    fs->fid 			= fid;

-    fs->direction 		= reply.drawDirection;

-    fs->min_char_or_byte2	= reply.minCharOrByte2;

-    fs->max_char_or_byte2 	= reply.maxCharOrByte2;

-    fs->min_byte1 		= reply.minByte1;

-    fs->max_byte1 		= reply.maxByte1;

-    fs->default_char 		= reply.defaultChar;

-    fs->all_chars_exist 	= reply.allCharsExist;

-    fs->ascent 			= cvtINT16toInt (reply.fontAscent);

-    fs->descent 		= cvtINT16toInt (reply.fontDescent);

-

-#ifdef MUSTCOPY

-    {

-	xCharInfo *xcip;

-

-	xcip = (xCharInfo *) &reply.minBounds;

-	fs->min_bounds.lbearing = cvtINT16toShort(xcip->leftSideBearing);

-	fs->min_bounds.rbearing = cvtINT16toShort(xcip->rightSideBearing);

-	fs->min_bounds.width = cvtINT16toShort(xcip->characterWidth);

-	fs->min_bounds.ascent = cvtINT16toShort(xcip->ascent);

-	fs->min_bounds.descent = cvtINT16toShort(xcip->descent);

-	fs->min_bounds.attributes = xcip->attributes;

-

-	xcip = (xCharInfo *) &reply.maxBounds;

-	fs->max_bounds.lbearing = cvtINT16toShort(xcip->leftSideBearing);

-	fs->max_bounds.rbearing =  cvtINT16toShort(xcip->rightSideBearing);

-	fs->max_bounds.width =  cvtINT16toShort(xcip->characterWidth);

-	fs->max_bounds.ascent =  cvtINT16toShort(xcip->ascent);

-	fs->max_bounds.descent =  cvtINT16toShort(xcip->descent);

-	fs->max_bounds.attributes = xcip->attributes;

-    }

-#else

-    /* XXX the next two statements won't work if short isn't 16 bits */

-    fs->min_bounds = * (XCharStruct *) &reply.minBounds;

-    fs->max_bounds = * (XCharStruct *) &reply.maxBounds;

-#endif /* MUSTCOPY */

-

-    fs->n_properties = reply.nFontProps;

-    /*

-     * if no properties defined for the font, then it is bad

-     * font, but shouldn't try to read nothing.

-     */

-    fs->properties = NULL;

-    if (fs->n_properties > 0) {

-	    nbytes = reply.nFontProps * sizeof(XFontProp);

-	    fs->properties = (XFontProp *) Xmalloc ((unsigned) nbytes);

-	    nbytes = reply.nFontProps * SIZEOF(xFontProp);

-	    if (! fs->properties) {

-		Xfree((char *) fs);

-		_XEatData(dpy, (unsigned long)

-			  (nbytes + reply.nCharInfos * SIZEOF(xCharInfo)));

-		return (XFontStruct *)NULL;

-	    }

-	    _XRead32 (dpy, (long *)fs->properties, nbytes);

-    }

-    /*

-     * If no characters in font, then it is a bad font, but

-     * shouldn't try to read nothing.

-     */

-    /* have to unpack charinfos on some machines (CRAY) */

-    fs->per_char = NULL;

-    if (reply.nCharInfos > 0){

-	nbytes = reply.nCharInfos * sizeof(XCharStruct);

-	if (! (fs->per_char = (XCharStruct *) Xmalloc ((unsigned) nbytes))) {

-	    if (fs->properties) Xfree((char *) fs->properties);

-	    Xfree((char *) fs);

-	    _XEatData(dpy, (unsigned long)

-			    (reply.nCharInfos * SIZEOF(xCharInfo)));

-	    return (XFontStruct *)NULL;

-	}

-

-#ifdef MUSTCOPY

-	{

-	    register XCharStruct *cs = fs->per_char;

-	    register int i;

-

-	    for (i = 0; i < reply.nCharInfos; i++, cs++) {

-		xCharInfo xcip;

-

-		_XRead(dpy, (char *)&xcip, SIZEOF(xCharInfo));

-		cs->lbearing = cvtINT16toShort(xcip.leftSideBearing);

-		cs->rbearing = cvtINT16toShort(xcip.rightSideBearing);

-		cs->width =  cvtINT16toShort(xcip.characterWidth);

-		cs->ascent =  cvtINT16toShort(xcip.ascent);

-		cs->descent =  cvtINT16toShort(xcip.descent);

-		cs->attributes = xcip.attributes;

-	    }

-	}

-#else

-	nbytes = reply.nCharInfos * SIZEOF(xCharInfo);

-	_XRead16 (dpy, (char *)fs->per_char, nbytes);

-#endif

-    }

-

-    /* call out to any extensions interested */

-    for (ext = dpy->ext_procs; ext; ext = ext->next)

-	if (ext->create_Font) (*ext->create_Font)(dpy, fs, &ext->codes);

-    return fs;

-}

-

-#ifdef USE_XF86BIGFONT

-

-/* Magic cookie for finding the right XExtData structure on the display's

-   extension list. */

-static int XF86BigfontNumber = 1040697125;

-

-static int

-_XF86BigfontFreeCodes (

-    XExtData *extension)

-{

-    /* Don't Xfree(extension->private_data) because it is on the same malloc

-       chunk as extension. */

-    /* Don't Xfree(extension->private_data->codes) because this is shared with

-       the display's ext_procs list. */

-    return 0;

-}

-

-static XF86BigfontCodes *

-_XF86BigfontCodes (

-    register Display *dpy)

-{

-    XEDataObject dpy_union;

-    XExtData *pData;

-    XF86BigfontCodes *pCodes;

-    char *envval;

-

-    dpy_union.display = dpy;

-

-    /* If the server is known to support the XF86Bigfont extension,

-     * return the extension codes. If the server is known to not support

-     * the extension, don't bother checking again.

-     */

-    pData = XFindOnExtensionList(XEHeadOfExtensionList(dpy_union),

-				 XF86BigfontNumber);

-    if (pData)

-	return (XF86BigfontCodes *) pData->private_data;

-

-    pData = (XExtData *) Xmalloc(sizeof(XExtData) + sizeof(XF86BigfontCodes));

-    if (!pData) {

-	/* Out of luck. */

-	return (XF86BigfontCodes *) NULL;

-    }

-

-    /* See if the server supports the XF86Bigfont extension. */

-    envval = getenv("XF86BIGFONT_DISABLE"); /* Let the user disable it. */

-    if (envval != NULL && envval[0] != '\0')

-	pCodes = NULL;

-    else {

-	XExtCodes *codes = XInitExtension(dpy, XF86BIGFONTNAME);

-	if (codes == NULL)

-	    pCodes = NULL;

-	else {

-	    pCodes = (XF86BigfontCodes *) &pData[1];

-	    pCodes->codes = codes;

-	}

-    }

-    pData->number = XF86BigfontNumber;

-    pData->private_data = (XPointer) pCodes;

-    pData->free_private = _XF86BigfontFreeCodes;

-    XAddToExtensionList(XEHeadOfExtensionList(dpy_union), pData);

-    if (pCodes) {

-	int result;

-

-	/* See if the server supports the XF86BigfontQueryFont request. */

-	xXF86BigfontQueryVersionReply reply;

-	register xXF86BigfontQueryVersionReq *req;

-

-	LockDisplay(dpy);

-

-	GetReq(XF86BigfontQueryVersion, req);

-	req->reqType = pCodes->codes->major_opcode;

-	req->xf86bigfontReqType = X_XF86BigfontQueryVersion;

-

-	result = _XReply (dpy, (xReply *) &reply,

-		(SIZEOF(xXF86BigfontQueryVersionReply) - SIZEOF(xReply)) >> 2,

-		xFalse);

-

-	UnlockDisplay(dpy);

-    	SyncHandle();

-

-	if(!result)

-	    goto ignore_extension;

-

-	/* No need to provide backward compatibility with version 1.0. It

-	   was never widely distributed. */

-	if (!(reply.majorVersion > 1

-	      || (reply.majorVersion == 1 && reply.minorVersion >= 1)))

-	    goto ignore_extension;

-

-	pCodes->serverSignature = reply.signature;

-	pCodes->serverCapabilities = reply.capabilities;

-    }

-    return pCodes;

-

-  ignore_extension:

-    /* No need to Xfree(pCodes) or Xfree(pCodes->codes), see

-       _XF86BigfontFreeCodes comment. */

-    pCodes = (XF86BigfontCodes *) NULL;

-    pData->private_data = (XPointer) pCodes;

-    return pCodes;

-}

-

-static int

-_XF86BigfontFreeNop (

-    XExtData *extension)

-{

-    return 0;

-}

-

-static XFontStruct *

-_XF86BigfontQueryFont (

-    register Display *dpy,

-    XF86BigfontCodes *extcodes,

-    Font fid,

-    unsigned long seq)

-{

-    register XFontStruct *fs;

-    register long nbytes;

-    xXF86BigfontQueryFontReply reply;

-    register xXF86BigfontQueryFontReq *req;

-    register _XExtension *ext;

-    _XAsyncHandler async1;

-    _XAsyncErrorState async1_state;

-    _XAsyncHandler async2;

-    _XAsyncErrorState async2_state;

-

-    if (seq) {

-	async1_state.min_sequence_number = seq;

-	async1_state.max_sequence_number = seq;

-	async1_state.error_code = BadName;

-	async1_state.major_opcode = X_OpenFont;

-	async1_state.minor_opcode = 0;

-	async1_state.error_count = 0;

-	async1.next = dpy->async_handlers;

-	async1.handler = _XAsyncErrorHandler;

-	async1.data = (XPointer)&async1_state;

-	dpy->async_handlers = &async1;

-    }

-

-    GetReq(XF86BigfontQueryFont, req);

-    req->reqType = extcodes->codes->major_opcode;

-    req->xf86bigfontReqType = X_XF86BigfontQueryFont;

-    req->id = fid;

-    req->flags = (extcodes->serverCapabilities & XF86Bigfont_CAP_LocalShm

-		  ? XF86Bigfont_FLAGS_Shm : 0);

-

-    /* The function _XQueryFont benefits from a "magic" error handler for

-       BadFont coming from a X_QueryFont request. (See function _XReply.)

-       We have to establish an error handler ourselves. */

-    async2_state.min_sequence_number = dpy->request;

-    async2_state.max_sequence_number = dpy->request;

-    async2_state.error_code = BadFont;

-    async2_state.major_opcode = extcodes->codes->major_opcode;

-    async2_state.minor_opcode = X_XF86BigfontQueryFont;

-    async2_state.error_count = 0;

-    async2.next = dpy->async_handlers;

-    async2.handler = _XAsyncErrorHandler;

-    async2.data = (XPointer)&async2_state;

-    dpy->async_handlers = &async2;

-

-    if (!_XReply (dpy, (xReply *) &reply,

-       ((SIZEOF(xXF86BigfontQueryFontReply) - SIZEOF(xReply)) >> 2), xFalse)) {

-	DeqAsyncHandler(dpy, &async2);

-	if (seq)

-	    DeqAsyncHandler(dpy, &async1);

-	return (XFontStruct *)NULL;

-    }

-    DeqAsyncHandler(dpy, &async2);

-    if (seq)

-	DeqAsyncHandler(dpy, &async1);

-    if (! (fs = (XFontStruct *) Xmalloc (sizeof (XFontStruct)))) {

-	_XEatData(dpy,

-	          reply.nFontProps * SIZEOF(xFontProp)

-	          + (reply.nCharInfos > 0 && reply.shmid == (CARD32)(-1)

-	             ? reply.nUniqCharInfos * SIZEOF(xCharInfo)

-	               + (reply.nCharInfos+1)/2 * 2 * sizeof(CARD16)

-	             : 0));

-	return (XFontStruct *)NULL;

-    }

-    fs->ext_data 		= NULL;

-    fs->fid 			= fid;

-    fs->direction 		= reply.drawDirection;

-    fs->min_char_or_byte2	= reply.minCharOrByte2;

-    fs->max_char_or_byte2 	= reply.maxCharOrByte2;

-    fs->min_byte1 		= reply.minByte1;

-    fs->max_byte1 		= reply.maxByte1;

-    fs->default_char 		= reply.defaultChar;

-    fs->all_chars_exist 	= reply.allCharsExist;

-    fs->ascent 			= cvtINT16toInt (reply.fontAscent);

-    fs->descent 		= cvtINT16toInt (reply.fontDescent);

-

-    /* XXX the next two statements won't work if short isn't 16 bits */

-    fs->min_bounds = * (XCharStruct *) &reply.minBounds;

-    fs->max_bounds = * (XCharStruct *) &reply.maxBounds;

-

-    fs->n_properties = reply.nFontProps;

-    /*

-     * if no properties defined for the font, then it is bad

-     * font, but shouldn't try to read nothing.

-     */

-    fs->properties = NULL;

-    if (fs->n_properties > 0) {

-	nbytes = reply.nFontProps * sizeof(XFontProp);

-	fs->properties = (XFontProp *) Xmalloc ((unsigned) nbytes);

-	nbytes = reply.nFontProps * SIZEOF(xFontProp);

-	if (! fs->properties) {

-	    Xfree((char *) fs);

-	    _XEatData(dpy,

-		      nbytes

-		      + (reply.nCharInfos > 0 && reply.shmid == (CARD32)(-1)

-		         ? reply.nUniqCharInfos * SIZEOF(xCharInfo)

-		           + (reply.nCharInfos+1)/2 * 2 * sizeof(CARD16)

-		         : 0));

-	    return (XFontStruct *)NULL;

-	}

-	_XRead32 (dpy, (long *)fs->properties, nbytes);

-    }

-

-    fs->per_char = NULL;

-    if (reply.nCharInfos > 0) {

-	/* fprintf(stderr, "received font metrics, nCharInfos = %d, nUniqCharInfos = %d, shmid = %d\n", reply.nCharInfos, reply.nUniqCharInfos, reply.shmid); */

-	if (reply.shmid == (CARD32)(-1)) {

-	    xCharInfo* pUniqCI;

-	    CARD16* pIndex2UniqIndex;

-	    int i;

-

-	    nbytes = reply.nUniqCharInfos * SIZEOF(xCharInfo)

-	             + (reply.nCharInfos+1)/2 * 2 * sizeof(CARD16);

-	    pUniqCI = (xCharInfo *) Xmalloc (nbytes);

-	    if (!pUniqCI) {

-		if (fs->properties) Xfree((char *) fs->properties);

-		Xfree((char *) fs);

-		_XEatData(dpy, nbytes);

-		return (XFontStruct *)NULL;

-	    }

-	    if (! (fs->per_char = (XCharStruct *) Xmalloc (reply.nCharInfos * sizeof(XCharStruct)))) {

-		Xfree((char *) pUniqCI);

-		if (fs->properties) Xfree((char *) fs->properties);

-		Xfree((char *) fs);

-		_XEatData(dpy, nbytes);

-		return (XFontStruct *)NULL;

-	    }

-	    _XRead16 (dpy, (char *) pUniqCI, nbytes);

-	    pIndex2UniqIndex = (CARD16*) (pUniqCI + reply.nUniqCharInfos);

-	    for (i = 0; i < reply.nCharInfos; i++) {

-		if (pIndex2UniqIndex[i] >= reply.nUniqCharInfos) {

-		    fprintf(stderr, "_XF86BigfontQueryFont: server returned wrong data\n");

-		    Xfree((char *) pUniqCI);

-		    if (fs->properties) Xfree((char *) fs->properties);

-		    Xfree((char *) fs);

-		    return (XFontStruct *)NULL;

-		}

-		/* XXX the next statement won't work if short isn't 16 bits */

-		fs->per_char[i] = * (XCharStruct *) &pUniqCI[pIndex2UniqIndex[i]];

-	    }

-	    Xfree((char *) pUniqCI);

-	} else {

-#ifdef HAS_SHM

-	    XExtData *pData;

-	    XEDataObject fs_union;

-	    char *addr;

-

-	    pData = (XExtData *) Xmalloc(sizeof(XExtData));

-	    if (!pData) {

-		if (fs->properties) Xfree((char *) fs->properties);

-		Xfree((char *) fs);

-		return (XFontStruct *)NULL;

-	    }

-

-	    /* In some cases (e.g. an ssh daemon forwarding an X session to

-	       a remote machine) it is possible that the X server thinks we

-	       are running on the same machine (because getpeername() and

-	       LocalClient() cannot know about the forwarding) but we are

-	       not really local. Therefore, when we attach the first shared

-	       memory segment, we verify that we are on the same machine as

-	       the X server by checking that 1. shmat() succeeds, 2. the

-	       segment has a sufficient size, 3. it contains the X server's

-	       signature. Then we set the CAP_VerifiedLocal bit to indicate

-	       the verification was successful. */

-

-	    if ((addr = shmat(reply.shmid, NULL, SHM_RDONLY)) == (char *)-1) {

-		if (extcodes->serverCapabilities & CAP_VerifiedLocal)

-		    fprintf(stderr, "_XF86BigfontQueryFont: could not attach shm segment\n");

-	        Xfree((char *) pData);

-	        if (fs->properties) Xfree((char *) fs->properties);

-	        Xfree((char *) fs);

-		/* Stop requesting shared memory transport from now on. */

-		extcodes->serverCapabilities &= ~ XF86Bigfont_CAP_LocalShm;

-	        return (XFontStruct *)NULL;

-	    }

-

-	    if (!(extcodes->serverCapabilities & CAP_VerifiedLocal)) {

-		struct shmid_ds buf;

-		if (!(shmctl(reply.shmid, IPC_STAT, &buf) >= 0

-		      && buf.shm_segsz >= reply.shmsegoffset + reply.nCharInfos * sizeof(XCharStruct) + sizeof(CARD32)

-		      && *(CARD32 *)(addr + reply.shmsegoffset + reply.nCharInfos * sizeof(XCharStruct)) == extcodes->serverSignature)) {

-		    shmdt(addr);

-		    Xfree((char *) pData);

-		    if (fs->properties) Xfree((char *) fs->properties);

-		    Xfree((char *) fs);

-		    /* Stop requesting shared memory transport from now on. */

-		    extcodes->serverCapabilities &= ~ XF86Bigfont_CAP_LocalShm;

-		    return (XFontStruct *)NULL;

-		}

-		extcodes->serverCapabilities |= CAP_VerifiedLocal;

-	    }

-

-	    pData->number = XF86BigfontNumber;

-	    pData->private_data = (XPointer) addr;

-	    pData->free_private = _XF86BigfontFreeNop;

-	    fs_union.font = fs;

-	    XAddToExtensionList(XEHeadOfExtensionList(fs_union), pData);

-

-	    fs->per_char = (XCharStruct *) (addr + reply.shmsegoffset);

-#else

-	    fprintf(stderr, "_XF86BigfontQueryFont: try recompiling libX11 with HasShm, Xserver has shm support\n");

-	    if (fs->properties) Xfree((char *) fs->properties);

-	    Xfree((char *) fs);

-	    /* Stop requesting shared memory transport from now on. */

-	    extcodes->serverCapabilities &= ~ XF86Bigfont_CAP_LocalShm;

-	    return (XFontStruct *)NULL;

-#endif

-	}

-    }

-

-    /* call out to any extensions interested */

-    for (ext = dpy->ext_procs; ext; ext = ext->next)

-	if (ext->create_Font) (*ext->create_Font)(dpy, fs, &ext->codes);

-    return fs;

-}

-

-void

-_XF86BigfontFreeFontMetrics (XFontStruct *fs)

-{

-#ifdef HAS_SHM

-    XExtData *pData;

-    XEDataObject fs_union;

-

-    fs_union.font = fs;

-    if ((pData = XFindOnExtensionList(XEHeadOfExtensionList(fs_union),

-				      XF86BigfontNumber)))

-	shmdt ((char *) pData->private_data);

-    else

-	Xfree ((char *) fs->per_char);

-#else

-    Xfree ((char *) fs->per_char);

-#endif

-}

-

-#endif /* USE_XF86BIGFONT */

-

-int _XF86LoadQueryLocaleFont(

-   Display *dpy,

-   _Xconst char *name,

-   XFontStruct **xfp,

-   Font *fidp)

-{

-    int l;

-    const char *charset, *p;

-    char buf[256];

-    XFontStruct *fs;

-    XLCd lcd;

-

-    if (!name)

-	return 0;

-    l = strlen(name);

-    if (l < 2 || name[l - 1] != '*' || name[l - 2] != '-')

-	return 0;

-    charset = NULL;

-    /* next three lines stolen from _XkbGetCharset() */

-    lcd = _XlcCurrentLC();

-    if ((lcd = _XlcCurrentLC()) != 0)

-	charset = XLC_PUBLIC(lcd, encoding_name);

-    if (!charset || (p = strrchr(charset, '-')) == 0 || p == charset || p[1] == 0 || (p[1] == '*' && p[2] == 0)) {

-	/* prefer latin1 if no encoding found */

-	charset = "ISO8859-1";

-	p = charset + 7;

-    }

-    if (l - 2 - (p - charset) < 0)

-	return 0;

-    if (_XlcNCompareISOLatin1(name + l - 2 - (p - charset), charset, p - charset))

-	return 0;

-    if (strlen(p + 1) + l - 1 >= sizeof(buf) - 1)

-	return 0;

-    strcpy(buf, name);

-    strcpy(buf + l - 1, p + 1);

-    fs = XLoadQueryFont(dpy, buf);

-    if (!fs)

-	return 0;

-    if (xfp) {

-	*xfp = fs;

-	if (fidp)

-	    *fidp = fs->fid;

-    } else if (fidp) {

-	if (fs->per_char) {

-#ifdef USE_XF86BIGFONT

-	    _XF86BigfontFreeFontMetrics(fs);

-#else

-	    Xfree ((char *) fs->per_char);

-#endif

-	}

-	_XFreeExtData(fs->ext_data);

-	if (fs->properties)

-	    Xfree ((char *) fs->properties);

-	*fidp = fs->fid;

-	Xfree ((char *) fs);

-    } else {

-	XFreeFont(dpy, fs);

-    }

-    return 1;

-}

+/*
+
+Copyright 1986, 1998  The Open Group
+Copyright (c) 2000  The XFree86 Project, Inc.
+
+Permission to use, copy, modify, distribute, and sell this software and its
+documentation for any purpose is hereby granted without fee, provided that
+the above copyright notice appear in all copies and that both that
+copyright notice and this permission notice appear in supporting
+documentation.
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+X CONSORTIUM OR THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
+
+Except as contained in this notice, the name of the X Consortium or of the
+XFree86 Project shall not be used in advertising or otherwise to promote the
+sale, use or other dealings in this Software without prior written
+authorization from the X Consortium and the XFree86 Project.
+
+*/
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+#include "Xlibint.h"
+
+#if defined(XF86BIGFONT) && !defined(MUSTCOPY)
+#define USE_XF86BIGFONT
+#endif
+#ifdef USE_XF86BIGFONT
+#include <sys/types.h>
+#ifdef HAS_SHM
+#include <sys/ipc.h>
+#include <sys/shm.h>
+#endif
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <X11/extensions/xf86bigfproto.h>
+#endif
+
+#include "Xlcint.h"
+#include "XlcPubI.h"
+
+
+static XFontStruct *_XQueryFont(
+    Display*		/* dpy */,
+    Font		/* fid */,
+    unsigned long	/* seq */
+);
+
+#ifdef USE_XF86BIGFONT
+
+/* Private data for this extension. */
+typedef struct {
+    XExtCodes *codes;
+    CARD32 serverSignature;
+    CARD32 serverCapabilities;
+} XF86BigfontCodes;
+
+/* Additional bit masks that can be set in serverCapabilities */
+#define CAP_VerifiedLocal 256
+
+static XF86BigfontCodes *_XF86BigfontCodes(
+    Display*		/* dpy */
+);
+
+static XFontStruct *_XF86BigfontQueryFont(
+    Display*		/* dpy */,
+    XF86BigfontCodes*	/* extcodes */,
+    Font		/* fid */,
+    unsigned long	/* seq */
+);
+
+void _XF86BigfontFreeFontMetrics(
+    XFontStruct*	/* fs */
+);
+
+#endif /* USE_XF86BIGFONT */
+
+
+XFontStruct *XLoadQueryFont(
+   register Display *dpy,
+   _Xconst char *name)
+{
+    XFontStruct *font_result;
+    register long nbytes;
+    Font fid;
+    xOpenFontReq *req;
+    unsigned long seq;
+#ifdef USE_XF86BIGFONT
+    XF86BigfontCodes *extcodes = _XF86BigfontCodes(dpy);
+#endif
+
+    if (_XF86LoadQueryLocaleFont(dpy, name, &font_result, (Font *)0))
+      return font_result;
+    LockDisplay(dpy);
+    GetReq(OpenFont, req);
+    seq = dpy->request;
+    nbytes = req->nbytes  = name ? strlen(name) : 0;
+    req->fid = fid = XAllocID(dpy);
+    req->length += (nbytes+3)>>2;
+    Data (dpy, name, nbytes);
+    font_result = NULL;
+#ifdef USE_XF86BIGFONT
+    if (extcodes) {
+	font_result = _XF86BigfontQueryFont(dpy, extcodes, fid, seq);
+	seq = 0;
+    }
+#endif
+    if (!font_result)
+	font_result = _XQueryFont(dpy, fid, seq);
+    UnlockDisplay(dpy);
+    SyncHandle();
+    return font_result;
+}
+
+XFontStruct *XQueryFont (
+    register Display *dpy,
+    Font fid)
+{
+    XFontStruct *font_result;
+#ifdef USE_XF86BIGFONT
+    XF86BigfontCodes *extcodes = _XF86BigfontCodes(dpy);
+#endif
+
+    LockDisplay(dpy);
+    font_result = NULL;
+#ifdef USE_XF86BIGFONT
+    if (extcodes) {
+	font_result = _XF86BigfontQueryFont(dpy, extcodes, fid, 0L);
+    }
+#endif
+    if (!font_result)
+	font_result = _XQueryFont(dpy, fid, 0L);
+    UnlockDisplay(dpy);
+    SyncHandle();
+    return font_result;
+}
+
+int
+XFreeFont(
+    register Display *dpy,
+    XFontStruct *fs)
+{
+    register xResourceReq *req;
+    register _XExtension *ext;
+
+    LockDisplay(dpy);
+    /* call out to any extensions interested */
+    for (ext = dpy->ext_procs; ext; ext = ext->next)
+	if (ext->free_Font) (*ext->free_Font)(dpy, fs, &ext->codes);
+    GetResReq (CloseFont, fs->fid, req);
+    UnlockDisplay(dpy);
+    SyncHandle();
+    if (fs->per_char) {
+#ifdef USE_XF86BIGFONT
+	_XF86BigfontFreeFontMetrics(fs);
+#else
+	Xfree ((char *) fs->per_char);
+#endif
+    }
+    _XFreeExtData(fs->ext_data);
+    if (fs->properties)
+	Xfree ((char *) fs->properties);
+    Xfree ((char *) fs);
+    return 1;
+}
+
+
+static XFontStruct *
+_XQueryFont (
+    register Display *dpy,
+    Font fid,
+    unsigned long seq)
+{
+    register XFontStruct *fs;
+    register long nbytes;
+    xQueryFontReply reply;
+    register xResourceReq *req;
+    register _XExtension *ext;
+    _XAsyncHandler async;
+    _XAsyncErrorState async_state;
+
+    if (seq) {
+	async_state.min_sequence_number = seq;
+	async_state.max_sequence_number = seq;
+	async_state.error_code = BadName;
+	async_state.major_opcode = X_OpenFont;
+	async_state.minor_opcode = 0;
+	async_state.error_count = 0;
+	async.next = dpy->async_handlers;
+	async.handler = _XAsyncErrorHandler;
+	async.data = (XPointer)&async_state;
+	dpy->async_handlers = &async;
+    }
+    GetResReq(QueryFont, fid, req);
+    if (!_XReply (dpy, (xReply *) &reply,
+       ((SIZEOF(xQueryFontReply) - SIZEOF(xReply)) >> 2), xFalse)) {
+	if (seq)
+	    DeqAsyncHandler(dpy, &async);
+	return (XFontStruct *)NULL;
+    }
+    if (seq)
+	DeqAsyncHandler(dpy, &async);
+    if (! (fs = (XFontStruct *) Xmalloc (sizeof (XFontStruct)))) {
+	_XEatData(dpy, (unsigned long)(reply.nFontProps * SIZEOF(xFontProp) +
+				       reply.nCharInfos * SIZEOF(xCharInfo)));
+	return (XFontStruct *)NULL;
+    }
+    fs->ext_data 		= NULL;
+    fs->fid 			= fid;
+    fs->direction 		= reply.drawDirection;
+    fs->min_char_or_byte2	= reply.minCharOrByte2;
+    fs->max_char_or_byte2 	= reply.maxCharOrByte2;
+    fs->min_byte1 		= reply.minByte1;
+    fs->max_byte1 		= reply.maxByte1;
+    fs->default_char 		= reply.defaultChar;
+    fs->all_chars_exist 	= reply.allCharsExist;
+    fs->ascent 			= cvtINT16toInt (reply.fontAscent);
+    fs->descent 		= cvtINT16toInt (reply.fontDescent);
+
+#ifdef MUSTCOPY
+    {
+	xCharInfo *xcip;
+
+	xcip = (xCharInfo *) &reply.minBounds;
+	fs->min_bounds.lbearing = cvtINT16toShort(xcip->leftSideBearing);
+	fs->min_bounds.rbearing = cvtINT16toShort(xcip->rightSideBearing);
+	fs->min_bounds.width = cvtINT16toShort(xcip->characterWidth);
+	fs->min_bounds.ascent = cvtINT16toShort(xcip->ascent);
+	fs->min_bounds.descent = cvtINT16toShort(xcip->descent);
+	fs->min_bounds.attributes = xcip->attributes;
+
+	xcip = (xCharInfo *) &reply.maxBounds;
+	fs->max_bounds.lbearing = cvtINT16toShort(xcip->leftSideBearing);
+	fs->max_bounds.rbearing =  cvtINT16toShort(xcip->rightSideBearing);
+	fs->max_bounds.width =  cvtINT16toShort(xcip->characterWidth);
+	fs->max_bounds.ascent =  cvtINT16toShort(xcip->ascent);
+	fs->max_bounds.descent =  cvtINT16toShort(xcip->descent);
+	fs->max_bounds.attributes = xcip->attributes;
+    }
+#else
+    /* XXX the next two statements won't work if short isn't 16 bits */
+    fs->min_bounds = * (XCharStruct *) &reply.minBounds;
+    fs->max_bounds = * (XCharStruct *) &reply.maxBounds;
+#endif /* MUSTCOPY */
+
+    fs->n_properties = reply.nFontProps;
+    /*
+     * if no properties defined for the font, then it is bad
+     * font, but shouldn't try to read nothing.
+     */
+    fs->properties = NULL;
+    if (fs->n_properties > 0) {
+	    nbytes = reply.nFontProps * sizeof(XFontProp);
+	    fs->properties = (XFontProp *) Xmalloc ((unsigned) nbytes);
+	    nbytes = reply.nFontProps * SIZEOF(xFontProp);
+	    if (! fs->properties) {
+		Xfree((char *) fs);
+		_XEatData(dpy, (unsigned long)
+			  (nbytes + reply.nCharInfos * SIZEOF(xCharInfo)));
+		return (XFontStruct *)NULL;
+	    }
+	    _XRead32 (dpy, (long *)fs->properties, nbytes);
+    }
+    /*
+     * If no characters in font, then it is a bad font, but
+     * shouldn't try to read nothing.
+     */
+    /* have to unpack charinfos on some machines (CRAY) */
+    fs->per_char = NULL;
+    if (reply.nCharInfos > 0){
+	nbytes = reply.nCharInfos * sizeof(XCharStruct);
+	if (! (fs->per_char = (XCharStruct *) Xmalloc ((unsigned) nbytes))) {
+	    if (fs->properties) Xfree((char *) fs->properties);
+	    Xfree((char *) fs);
+	    _XEatData(dpy, (unsigned long)
+			    (reply.nCharInfos * SIZEOF(xCharInfo)));
+	    return (XFontStruct *)NULL;
+	}
+
+#ifdef MUSTCOPY
+	{
+	    register XCharStruct *cs = fs->per_char;
+	    register int i;
+
+	    for (i = 0; i < reply.nCharInfos; i++, cs++) {
+		xCharInfo xcip;
+
+		_XRead(dpy, (char *)&xcip, SIZEOF(xCharInfo));
+		cs->lbearing = cvtINT16toShort(xcip.leftSideBearing);
+		cs->rbearing = cvtINT16toShort(xcip.rightSideBearing);
+		cs->width =  cvtINT16toShort(xcip.characterWidth);
+		cs->ascent =  cvtINT16toShort(xcip.ascent);
+		cs->descent =  cvtINT16toShort(xcip.descent);
+		cs->attributes = xcip.attributes;
+	    }
+	}
+#else
+	nbytes = reply.nCharInfos * SIZEOF(xCharInfo);
+	_XRead16 (dpy, (char *)fs->per_char, nbytes);
+#endif
+    }
+
+    /* call out to any extensions interested */
+    for (ext = dpy->ext_procs; ext; ext = ext->next)
+	if (ext->create_Font) (*ext->create_Font)(dpy, fs, &ext->codes);
+    return fs;
+}
+
+#ifdef USE_XF86BIGFONT
+
+/* Magic cookie for finding the right XExtData structure on the display's
+   extension list. */
+static int XF86BigfontNumber = 1040697125;
+
+static int
+_XF86BigfontFreeCodes (
+    XExtData *extension)
+{
+    /* Don't Xfree(extension->private_data) because it is on the same malloc
+       chunk as extension. */
+    /* Don't Xfree(extension->private_data->codes) because this is shared with
+       the display's ext_procs list. */
+    return 0;
+}
+
+static XF86BigfontCodes *
+_XF86BigfontCodes (
+    register Display *dpy)
+{
+    XEDataObject dpy_union;
+    XExtData *pData;
+    XF86BigfontCodes *pCodes;
+    char *envval;
+
+    dpy_union.display = dpy;
+
+    /* If the server is known to support the XF86Bigfont extension,
+     * return the extension codes. If the server is known to not support
+     * the extension, don't bother checking again.
+     */
+    pData = XFindOnExtensionList(XEHeadOfExtensionList(dpy_union),
+				 XF86BigfontNumber);
+    if (pData)
+	return (XF86BigfontCodes *) pData->private_data;
+
+    pData = (XExtData *) Xmalloc(sizeof(XExtData) + sizeof(XF86BigfontCodes));
+    if (!pData) {
+	/* Out of luck. */
+	return (XF86BigfontCodes *) NULL;
+    }
+
+    /* See if the server supports the XF86Bigfont extension. */
+    envval = getenv("XF86BIGFONT_DISABLE"); /* Let the user disable it. */
+    if (envval != NULL && envval[0] != '\0')
+	pCodes = NULL;
+    else {
+	XExtCodes *codes = XInitExtension(dpy, XF86BIGFONTNAME);
+	if (codes == NULL)
+	    pCodes = NULL;
+	else {
+	    pCodes = (XF86BigfontCodes *) &pData[1];
+	    pCodes->codes = codes;
+	}
+    }
+    pData->number = XF86BigfontNumber;
+    pData->private_data = (XPointer) pCodes;
+    pData->free_private = _XF86BigfontFreeCodes;
+    XAddToExtensionList(XEHeadOfExtensionList(dpy_union), pData);
+    if (pCodes) {
+	int result;
+
+	/* See if the server supports the XF86BigfontQueryFont request. */
+	xXF86BigfontQueryVersionReply reply;
+	register xXF86BigfontQueryVersionReq *req;
+
+	LockDisplay(dpy);
+
+	GetReq(XF86BigfontQueryVersion, req);
+	req->reqType = pCodes->codes->major_opcode;
+	req->xf86bigfontReqType = X_XF86BigfontQueryVersion;
+
+	result = _XReply (dpy, (xReply *) &reply,
+		(SIZEOF(xXF86BigfontQueryVersionReply) - SIZEOF(xReply)) >> 2,
+		xFalse);
+
+	UnlockDisplay(dpy);
+    	SyncHandle();
+
+	if(!result)
+	    goto ignore_extension;
+
+	/* No need to provide backward compatibility with version 1.0. It
+	   was never widely distributed. */
+	if (!(reply.majorVersion > 1
+	      || (reply.majorVersion == 1 && reply.minorVersion >= 1)))
+	    goto ignore_extension;
+
+	pCodes->serverSignature = reply.signature;
+	pCodes->serverCapabilities = reply.capabilities;
+    }
+    return pCodes;
+
+  ignore_extension:
+    /* No need to Xfree(pCodes) or Xfree(pCodes->codes), see
+       _XF86BigfontFreeCodes comment. */
+    pCodes = (XF86BigfontCodes *) NULL;
+    pData->private_data = (XPointer) pCodes;
+    return pCodes;
+}
+
+static int
+_XF86BigfontFreeNop (
+    XExtData *extension)
+{
+    return 0;
+}
+
+static XFontStruct *
+_XF86BigfontQueryFont (
+    register Display *dpy,
+    XF86BigfontCodes *extcodes,
+    Font fid,
+    unsigned long seq)
+{
+    register XFontStruct *fs;
+    register long nbytes;
+    xXF86BigfontQueryFontReply reply;
+    register xXF86BigfontQueryFontReq *req;
+    register _XExtension *ext;
+    _XAsyncHandler async1;
+    _XAsyncErrorState async1_state;
+    _XAsyncHandler async2;
+    _XAsyncErrorState async2_state;
+
+    if (seq) {
+	async1_state.min_sequence_number = seq;
+	async1_state.max_sequence_number = seq;
+	async1_state.error_code = BadName;
+	async1_state.major_opcode = X_OpenFont;
+	async1_state.minor_opcode = 0;
+	async1_state.error_count = 0;
+	async1.next = dpy->async_handlers;
+	async1.handler = _XAsyncErrorHandler;
+	async1.data = (XPointer)&async1_state;
+	dpy->async_handlers = &async1;
+    }
+
+    GetReq(XF86BigfontQueryFont, req);
+    req->reqType = extcodes->codes->major_opcode;
+    req->xf86bigfontReqType = X_XF86BigfontQueryFont;
+    req->id = fid;
+    req->flags = (extcodes->serverCapabilities & XF86Bigfont_CAP_LocalShm
+		  ? XF86Bigfont_FLAGS_Shm : 0);
+
+    /* The function _XQueryFont benefits from a "magic" error handler for
+       BadFont coming from a X_QueryFont request. (See function _XReply.)
+       We have to establish an error handler ourselves. */
+    async2_state.min_sequence_number = dpy->request;
+    async2_state.max_sequence_number = dpy->request;
+    async2_state.error_code = BadFont;
+    async2_state.major_opcode = extcodes->codes->major_opcode;
+    async2_state.minor_opcode = X_XF86BigfontQueryFont;
+    async2_state.error_count = 0;
+    async2.next = dpy->async_handlers;
+    async2.handler = _XAsyncErrorHandler;
+    async2.data = (XPointer)&async2_state;
+    dpy->async_handlers = &async2;
+
+    if (!_XReply (dpy, (xReply *) &reply,
+       ((SIZEOF(xXF86BigfontQueryFontReply) - SIZEOF(xReply)) >> 2), xFalse)) {
+	DeqAsyncHandler(dpy, &async2);
+	if (seq)
+	    DeqAsyncHandler(dpy, &async1);
+	return (XFontStruct *)NULL;
+    }
+    DeqAsyncHandler(dpy, &async2);
+    if (seq)
+	DeqAsyncHandler(dpy, &async1);
+    if (! (fs = (XFontStruct *) Xmalloc (sizeof (XFontStruct)))) {
+	_XEatData(dpy,
+	          reply.nFontProps * SIZEOF(xFontProp)
+	          + (reply.nCharInfos > 0 && reply.shmid == (CARD32)(-1)
+	             ? reply.nUniqCharInfos * SIZEOF(xCharInfo)
+	               + (reply.nCharInfos+1)/2 * 2 * sizeof(CARD16)
+	             : 0));
+	return (XFontStruct *)NULL;
+    }
+    fs->ext_data 		= NULL;
+    fs->fid 			= fid;
+    fs->direction 		= reply.drawDirection;
+    fs->min_char_or_byte2	= reply.minCharOrByte2;
+    fs->max_char_or_byte2 	= reply.maxCharOrByte2;
+    fs->min_byte1 		= reply.minByte1;
+    fs->max_byte1 		= reply.maxByte1;
+    fs->default_char 		= reply.defaultChar;
+    fs->all_chars_exist 	= reply.allCharsExist;
+    fs->ascent 			= cvtINT16toInt (reply.fontAscent);
+    fs->descent 		= cvtINT16toInt (reply.fontDescent);
+
+    /* XXX the next two statements won't work if short isn't 16 bits */
+    fs->min_bounds = * (XCharStruct *) &reply.minBounds;
+    fs->max_bounds = * (XCharStruct *) &reply.maxBounds;
+
+    fs->n_properties = reply.nFontProps;
+    /*
+     * if no properties defined for the font, then it is bad
+     * font, but shouldn't try to read nothing.
+     */
+    fs->properties = NULL;
+    if (fs->n_properties > 0) {
+	nbytes = reply.nFontProps * sizeof(XFontProp);
+	fs->properties = (XFontProp *) Xmalloc ((unsigned) nbytes);
+	nbytes = reply.nFontProps * SIZEOF(xFontProp);
+	if (! fs->properties) {
+	    Xfree((char *) fs);
+	    _XEatData(dpy,
+		      nbytes
+		      + (reply.nCharInfos > 0 && reply.shmid == (CARD32)(-1)
+		         ? reply.nUniqCharInfos * SIZEOF(xCharInfo)
+		           + (reply.nCharInfos+1)/2 * 2 * sizeof(CARD16)
+		         : 0));
+	    return (XFontStruct *)NULL;
+	}
+	_XRead32 (dpy, (long *)fs->properties, nbytes);
+    }
+
+    fs->per_char = NULL;
+    if (reply.nCharInfos > 0) {
+	/* fprintf(stderr, "received font metrics, nCharInfos = %d, nUniqCharInfos = %d, shmid = %d\n", reply.nCharInfos, reply.nUniqCharInfos, reply.shmid); */
+	if (reply.shmid == (CARD32)(-1)) {
+	    xCharInfo* pUniqCI;
+	    CARD16* pIndex2UniqIndex;
+	    int i;
+
+	    nbytes = reply.nUniqCharInfos * SIZEOF(xCharInfo)
+	             + (reply.nCharInfos+1)/2 * 2 * sizeof(CARD16);
+	    pUniqCI = (xCharInfo *) Xmalloc (nbytes);
+	    if (!pUniqCI) {
+		if (fs->properties) Xfree((char *) fs->properties);
+		Xfree((char *) fs);
+		_XEatData(dpy, nbytes);
+		return (XFontStruct *)NULL;
+	    }
+	    if (! (fs->per_char = (XCharStruct *) Xmalloc (reply.nCharInfos * sizeof(XCharStruct)))) {
+		Xfree((char *) pUniqCI);
+		if (fs->properties) Xfree((char *) fs->properties);
+		Xfree((char *) fs);
+		_XEatData(dpy, nbytes);
+		return (XFontStruct *)NULL;
+	    }
+	    _XRead16 (dpy, (char *) pUniqCI, nbytes);
+	    pIndex2UniqIndex = (CARD16*) (pUniqCI + reply.nUniqCharInfos);
+	    for (i = 0; i < reply.nCharInfos; i++) {
+		if (pIndex2UniqIndex[i] >= reply.nUniqCharInfos) {
+		    fprintf(stderr, "_XF86BigfontQueryFont: server returned wrong data\n");
+		    Xfree((char *) pUniqCI);
+		    if (fs->properties) Xfree((char *) fs->properties);
+		    Xfree((char *) fs);
+		    return (XFontStruct *)NULL;
+		}
+		/* XXX the next statement won't work if short isn't 16 bits */
+		fs->per_char[i] = * (XCharStruct *) &pUniqCI[pIndex2UniqIndex[i]];
+	    }
+	    Xfree((char *) pUniqCI);
+	} else {
+#ifdef HAS_SHM
+	    XExtData *pData;
+	    XEDataObject fs_union;
+	    char *addr;
+
+	    pData = (XExtData *) Xmalloc(sizeof(XExtData));
+	    if (!pData) {
+		if (fs->properties) Xfree((char *) fs->properties);
+		Xfree((char *) fs);
+		return (XFontStruct *)NULL;
+	    }
+
+	    /* In some cases (e.g. an ssh daemon forwarding an X session to
+	       a remote machine) it is possible that the X server thinks we
+	       are running on the same machine (because getpeername() and
+	       LocalClient() cannot know about the forwarding) but we are
+	       not really local. Therefore, when we attach the first shared
+	       memory segment, we verify that we are on the same machine as
+	       the X server by checking that 1. shmat() succeeds, 2. the
+	       segment has a sufficient size, 3. it contains the X server's
+	       signature. Then we set the CAP_VerifiedLocal bit to indicate
+	       the verification was successful. */
+
+	    if ((addr = shmat(reply.shmid, NULL, SHM_RDONLY)) == (char *)-1) {
+		if (extcodes->serverCapabilities & CAP_VerifiedLocal)
+		    fprintf(stderr, "_XF86BigfontQueryFont: could not attach shm segment\n");
+	        Xfree((char *) pData);
+	        if (fs->properties) Xfree((char *) fs->properties);
+	        Xfree((char *) fs);
+		/* Stop requesting shared memory transport from now on. */
+		extcodes->serverCapabilities &= ~ XF86Bigfont_CAP_LocalShm;
+	        return (XFontStruct *)NULL;
+	    }
+
+	    if (!(extcodes->serverCapabilities & CAP_VerifiedLocal)) {
+		struct shmid_ds buf;
+		if (!(shmctl(reply.shmid, IPC_STAT, &buf) >= 0
+		      && buf.shm_segsz >= reply.shmsegoffset + reply.nCharInfos * sizeof(XCharStruct) + sizeof(CARD32)
+		      && *(CARD32 *)(addr + reply.shmsegoffset + reply.nCharInfos * sizeof(XCharStruct)) == extcodes->serverSignature)) {
+		    shmdt(addr);
+		    Xfree((char *) pData);
+		    if (fs->properties) Xfree((char *) fs->properties);
+		    Xfree((char *) fs);
+		    /* Stop requesting shared memory transport from now on. */
+		    extcodes->serverCapabilities &= ~ XF86Bigfont_CAP_LocalShm;
+		    return (XFontStruct *)NULL;
+		}
+		extcodes->serverCapabilities |= CAP_VerifiedLocal;
+	    }
+
+	    pData->number = XF86BigfontNumber;
+	    pData->private_data = (XPointer) addr;
+	    pData->free_private = _XF86BigfontFreeNop;
+	    fs_union.font = fs;
+	    XAddToExtensionList(XEHeadOfExtensionList(fs_union), pData);
+
+	    fs->per_char = (XCharStruct *) (addr + reply.shmsegoffset);
+#else
+	    fprintf(stderr, "_XF86BigfontQueryFont: try recompiling libX11 with HasShm, Xserver has shm support\n");
+	    if (fs->properties) Xfree((char *) fs->properties);
+	    Xfree((char *) fs);
+	    /* Stop requesting shared memory transport from now on. */
+	    extcodes->serverCapabilities &= ~ XF86Bigfont_CAP_LocalShm;
+	    return (XFontStruct *)NULL;
+#endif
+	}
+    }
+
+    /* call out to any extensions interested */
+    for (ext = dpy->ext_procs; ext; ext = ext->next)
+	if (ext->create_Font) (*ext->create_Font)(dpy, fs, &ext->codes);
+    return fs;
+}
+
+void
+_XF86BigfontFreeFontMetrics (XFontStruct *fs)
+{
+#ifdef HAS_SHM
+    XExtData *pData;
+    XEDataObject fs_union;
+
+    fs_union.font = fs;
+    if ((pData = XFindOnExtensionList(XEHeadOfExtensionList(fs_union),
+				      XF86BigfontNumber)))
+	shmdt ((char *) pData->private_data);
+    else
+	Xfree ((char *) fs->per_char);
+#else
+    Xfree ((char *) fs->per_char);
+#endif
+}
+
+#endif /* USE_XF86BIGFONT */
+
+int _XF86LoadQueryLocaleFont(
+   Display *dpy,
+   _Xconst char *name,
+   XFontStruct **xfp,
+   Font *fidp)
+{
+    int l;
+    const char *charset, *p;
+    char buf[256];
+    XFontStruct *fs;
+    XLCd lcd;
+
+    if (!name)
+	return 0;
+    l = strlen(name);
+    if (l < 2 || name[l - 1] != '*' || name[l - 2] != '-')
+	return 0;
+    charset = NULL;
+    /* next three lines stolen from _XkbGetCharset() */
+    lcd = _XlcCurrentLC();
+    if ((lcd = _XlcCurrentLC()) != 0)
+	charset = XLC_PUBLIC(lcd, encoding_name);
+    if (!charset || (p = strrchr(charset, '-')) == 0 || p == charset || p[1] == 0 || (p[1] == '*' && p[2] == 0)) {
+	/* prefer latin1 if no encoding found */
+	charset = "ISO8859-1";
+	p = charset + 7;
+    }
+    if (l - 2 - (p - charset) < 0)
+	return 0;
+    if (_XlcNCompareISOLatin1(name + l - 2 - (p - charset), charset, p - charset))
+	return 0;
+    if (strlen(p + 1) + l - 1 >= sizeof(buf) - 1)
+	return 0;
+    strcpy(buf, name);
+    strcpy(buf + l - 1, p + 1);
+    fs = XLoadQueryFont(dpy, buf);
+    if (!fs)
+	return 0;
+    if (xfp) {
+	*xfp = fs;
+	if (fidp)
+	    *fidp = fs->fid;
+    } else if (fidp) {
+	if (fs->per_char) {
+#ifdef USE_XF86BIGFONT
+	    _XF86BigfontFreeFontMetrics(fs);
+#else
+	    Xfree ((char *) fs->per_char);
+#endif
+	}
+	_XFreeExtData(fs->ext_data);
+	if (fs->properties)
+	    Xfree ((char *) fs->properties);
+	*fidp = fs->fid;
+	Xfree ((char *) fs);
+    } else {
+	XFreeFont(dpy, fs);
+    }
+    return 1;
+}
diff --git a/pixman/pixman/pixman-region.c b/pixman/pixman/pixman-region.c
index 52e26dd5c..142493b77 100644
--- a/pixman/pixman/pixman-region.c
+++ b/pixman/pixman/pixman-region.c
@@ -1,2769 +1,2770 @@
-/*

- * Copyright 1987, 1988, 1989, 1998  The Open Group

- * 

- * Permission to use, copy, modify, distribute, and sell this software and its

- * documentation for any purpose is hereby granted without fee, provided that

- * the above copyright notice appear in all copies and that both that

- * copyright notice and this permission notice appear in supporting

- * documentation.

- * 

- * The above copyright notice and this permission notice shall be included in

- * all copies or substantial portions of the Software.

- * 

- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE

- * OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN

- * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN

- * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

- * 

- * Except as contained in this notice, the name of The Open Group shall not be

- * used in advertising or otherwise to promote the sale, use or other dealings

- * in this Software without prior written authorization from The Open Group.

- * 

- * Copyright 1987, 1988, 1989 by

- * Digital Equipment Corporation, Maynard, Massachusetts.

- * 

- *                    All Rights Reserved

- * 

- * Permission to use, copy, modify, and distribute this software and its

- * documentation for any purpose and without fee is hereby granted,

- * provided that the above copyright notice appear in all copies and that

- * both that copyright notice and this permission notice appear in

- * supporting documentation, and that the name of Digital not be

- * used in advertising or publicity pertaining to distribution of the

- * software without specific, written prior permission.

- * 

- * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING

- * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL

- * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR

- * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,

- * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,

- * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS

- * SOFTWARE.

- *

- * Copyright © 1998 Keith Packard

- *

- * Permission to use, copy, modify, distribute, and sell this software and its

- * documentation for any purpose is hereby granted without fee, provided that

- * the above copyright notice appear in all copies and that both that

- * copyright notice and this permission notice appear in supporting

- * documentation, and that the name of Keith Packard not be used in

- * advertising or publicity pertaining to distribution of the software without

- * specific, written prior permission.  Keith Packard makes no

- * representations about the suitability of this software for any purpose.  It

- * is provided "as is" without express or implied warranty.

- *

- * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,

- * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO

- * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR

- * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,

- * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER

- * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR

- * PERFORMANCE OF THIS SOFTWARE.

- */

-

-#include <stdlib.h>

-#include <limits.h>

-#include <string.h>

-#include <stdio.h>

-#include "pixman-private.h"

-

-#define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)

-/* not a region */

-#define PIXREGION_NAR(reg)      ((reg)->data == pixman_broken_data)

-#define PIXREGION_NUMRECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)

-#define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)

-#define PIXREGION_RECTS(reg) \

-    ((reg)->data ? (box_type_t *)((reg)->data + 1) \

-     : &(reg)->extents)

-#define PIXREGION_BOXPTR(reg) ((box_type_t *)((reg)->data + 1))

-#define PIXREGION_BOX(reg, i) (&PIXREGION_BOXPTR (reg)[i])

-#define PIXREGION_TOP(reg) PIXREGION_BOX (reg, (reg)->data->numRects)

-#define PIXREGION_END(reg) PIXREGION_BOX (reg, (reg)->data->numRects - 1)

-

-#define GOOD_RECT(rect) ((rect)->x1 < (rect)->x2 && (rect)->y1 < (rect)->y2)

-#define BAD_RECT(rect) ((rect)->x1 > (rect)->x2 || (rect)->y1 > (rect)->y2)

-

-#ifdef DEBUG

-

-#define GOOD(reg)							\

-    do									\

-    {									\

-	if (!PREFIX (_selfcheck (reg)))					\

-	    _pixman_log_error (FUNC, "Malformed region " # reg);	\

-    } while (0)

-

-#else

-

-#define GOOD(reg)

-

-#endif

-

-static const box_type_t PREFIX (_empty_box_) = { 0, 0, 0, 0 };

-static const region_data_type_t PREFIX (_empty_data_) = { 0, 0 };

-static const region_data_type_t PREFIX (_broken_data_) = { 0, 0 };

-

-static box_type_t *pixman_region_empty_box =

-    (box_type_t *)&PREFIX (_empty_box_);

-static region_data_type_t *pixman_region_empty_data =

-    (region_data_type_t *)&PREFIX (_empty_data_);

-static region_data_type_t *pixman_broken_data =

-    (region_data_type_t *)&PREFIX (_broken_data_);

-

-static pixman_bool_t

-pixman_break (region_type_t *region);

-

-/*

- * The functions in this file implement the Region abstraction used extensively

- * throughout the X11 sample server. A Region is simply a set of disjoint

- * (non-overlapping) rectangles, plus an "extent" rectangle which is the

- * smallest single rectangle that contains all the non-overlapping rectangles.

- *

- * A Region is implemented as a "y-x-banded" array of rectangles.  This array

- * imposes two degrees of order.  First, all rectangles are sorted by top side

- * y coordinate first (y1), and then by left side x coordinate (x1).

- *

- * Furthermore, the rectangles are grouped into "bands".  Each rectangle in a

- * band has the same top y coordinate (y1), and each has the same bottom y

- * coordinate (y2).  Thus all rectangles in a band differ only in their left

- * and right side (x1 and x2).  Bands are implicit in the array of rectangles:

- * there is no separate list of band start pointers.

- *

- * The y-x band representation does not minimize rectangles.  In particular,

- * if a rectangle vertically crosses a band (the rectangle has scanlines in

- * the y1 to y2 area spanned by the band), then the rectangle may be broken

- * down into two or more smaller rectangles stacked one atop the other.

- *

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

- *  |         |				    |         |		    band 0

- *  |         |  --------		    -----------  --------

- *  |         |  |      |  in y-x banded    |         |  |      |   band 1

- *  |         |  |      |  form is	    |         |  |      |

- *  -----------  |      |		    -----------  --------

- *               |      |				 |      |   band 2

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

- *

- * An added constraint on the rectangles is that they must cover as much

- * horizontal area as possible: no two rectangles within a band are allowed

- * to touch.

- *

- * Whenever possible, bands will be merged together to cover a greater vertical

- * distance (and thus reduce the number of rectangles). Two bands can be merged

- * only if the bottom of one touches the top of the other and they have

- * rectangles in the same places (of the same width, of course).

- *

- * Adam de Boor wrote most of the original region code.  Joel McCormack

- * substantially modified or rewrote most of the core arithmetic routines, and

- * added pixman_region_validate in order to support several speed improvements

- * to pixman_region_validate_tree.  Bob Scheifler changed the representation

- * to be more compact when empty or a single rectangle, and did a bunch of

- * gratuitous reformatting. Carl Worth did further gratuitous reformatting

- * while re-merging the server and client region code into libpixregion.

- * Soren Sandmann did even more gratuitous reformatting.

- */

-

-/*  true iff two Boxes overlap */

-#define EXTENTCHECK(r1, r2)	   \

-    (!( ((r1)->x2 <= (r2)->x1)  || \

-        ((r1)->x1 >= (r2)->x2)  || \

-        ((r1)->y2 <= (r2)->y1)  || \

-        ((r1)->y1 >= (r2)->y2) ) )

-

-/* true iff (x,y) is in Box */

-#define INBOX(r, x, y)	\

-    ( ((r)->x2 >  x) && \

-      ((r)->x1 <= x) && \

-      ((r)->y2 >  y) && \

-      ((r)->y1 <= y) )

-

-/* true iff Box r1 contains Box r2 */

-#define SUBSUMES(r1, r2)	\

-    ( ((r1)->x1 <= (r2)->x1) && \

-      ((r1)->x2 >= (r2)->x2) && \

-      ((r1)->y1 <= (r2)->y1) && \

-      ((r1)->y2 >= (r2)->y2) )

-

-static size_t

-PIXREGION_SZOF (size_t n)

-{

-    size_t size = n * sizeof(box_type_t);

-    

-    if (n > UINT32_MAX / sizeof(box_type_t))

-	return 0;

-

-    if (sizeof(region_data_type_t) > UINT32_MAX - size)

-	return 0;

-

-    return size + sizeof(region_data_type_t);

-}

-

-static void *

-alloc_data (size_t n)

-{

-    size_t sz = PIXREGION_SZOF (n);

-

-    if (!sz)

-	return NULL;

-

-    return malloc (sz);

-}

-

-#define FREE_DATA(reg) if ((reg)->data && (reg)->data->size) free ((reg)->data)

-

-#define RECTALLOC_BAIL(region, n, bail)					\

-    do									\

-    {									\

-	if (!(region)->data ||						\

-	    (((region)->data->numRects + (n)) > (region)->data->size))	\

-	{								\

-	    if (!pixman_rect_alloc (region, n))				\

-		goto bail;						\

-	}								\

-    } while (0)

-

-#define RECTALLOC(region, n)						\

-    do									\

-    {									\

-	if (!(region)->data ||						\

-	    (((region)->data->numRects + (n)) > (region)->data->size))	\

-	{								\

-	    if (!pixman_rect_alloc (region, n)) {			\

-		return FALSE;						\

-	    }								\

-	}								\

-    } while (0)

-

-#define ADDRECT(next_rect, nx1, ny1, nx2, ny2)      \

-    do						    \

-    {						    \

-	next_rect->x1 = nx1;                        \

-	next_rect->y1 = ny1;                        \

-	next_rect->x2 = nx2;                        \

-	next_rect->y2 = ny2;                        \

-	next_rect++;                                \

-    }						    \

-    while (0)

-

-#define NEWRECT(region, next_rect, nx1, ny1, nx2, ny2)			\

-    do									\

-    {									\

-	if (!(region)->data ||						\

-	    ((region)->data->numRects == (region)->data->size))		\

-	{								\

-	    if (!pixman_rect_alloc (region, 1))				\

-		return FALSE;						\

-	    next_rect = PIXREGION_TOP (region);				\

-	}								\

-	ADDRECT (next_rect, nx1, ny1, nx2, ny2);			\

-	region->data->numRects++;					\

-	critical_if_fail (region->data->numRects <= region->data->size);		\

-    } while (0)

-

-#define DOWNSIZE(reg, numRects)						\

-    do									\

-    {									\

-	if (((numRects) < ((reg)->data->size >> 1)) &&			\

-	    ((reg)->data->size > 50))					\

-	{								\

-	    region_data_type_t * new_data;				\

-	    size_t data_size = PIXREGION_SZOF (numRects);		\

-									\

-	    if (!data_size)						\

-	    {								\

-		new_data = NULL;					\

-	    }								\

-	    else							\

-	    {								\

-		new_data = (region_data_type_t *)			\

-		    realloc ((reg)->data, data_size);			\

-	    }								\

-									\

-	    if (new_data)						\

-	    {								\

-		new_data->size = (numRects);				\

-		(reg)->data = new_data;					\

-	    }								\

-	}								\

-    } while (0)

-

-PIXMAN_EXPORT pixman_bool_t

-PREFIX (_equal) (region_type_t *reg1, region_type_t *reg2)

-{

-    int i;

-    box_type_t *rects1;

-    box_type_t *rects2;

-

-    if (reg1->extents.x1 != reg2->extents.x1)

-	return FALSE;

-    

-    if (reg1->extents.x2 != reg2->extents.x2)

-	return FALSE;

-    

-    if (reg1->extents.y1 != reg2->extents.y1)

-	return FALSE;

-    

-    if (reg1->extents.y2 != reg2->extents.y2)

-	return FALSE;

-    

-    if (PIXREGION_NUMRECTS (reg1) != PIXREGION_NUMRECTS (reg2))

-	return FALSE;

-

-    rects1 = PIXREGION_RECTS (reg1);

-    rects2 = PIXREGION_RECTS (reg2);

-    

-    for (i = 0; i != PIXREGION_NUMRECTS (reg1); i++)

-    {

-	if (rects1[i].x1 != rects2[i].x1)

-	    return FALSE;

-	

-	if (rects1[i].x2 != rects2[i].x2)

-	    return FALSE;

-	

-	if (rects1[i].y1 != rects2[i].y1)

-	    return FALSE;

-	

-	if (rects1[i].y2 != rects2[i].y2)

-	    return FALSE;

-    }

-

-    return TRUE;

-}

-

-int

-PREFIX (_print) (region_type_t *rgn)

-{

-    int num, size;

-    int i;

-    box_type_t * rects;

-

-    num = PIXREGION_NUMRECTS (rgn);

-    size = PIXREGION_SIZE (rgn);

-    rects = PIXREGION_RECTS (rgn);

-

-    fprintf (stderr, "num: %d size: %d\n", num, size);

-    fprintf (stderr, "extents: %d %d %d %d\n",

-             rgn->extents.x1,

-	     rgn->extents.y1,

-	     rgn->extents.x2,

-	     rgn->extents.y2);

-    

-    for (i = 0; i < num; i++)

-    {

-	fprintf (stderr, "%d %d %d %d \n",

-	         rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);

-    }

-    

-    fprintf (stderr, "\n");

-

-    return(num);

-}

-

-

-PIXMAN_EXPORT void

-PREFIX (_init) (region_type_t *region)

-{

-    region->extents = *pixman_region_empty_box;

-    region->data = pixman_region_empty_data;

-}

-

-PIXMAN_EXPORT void

-PREFIX (_init_rect) (region_type_t *	region,

-                     int		x,

-		     int		y,

-		     unsigned int	width,

-		     unsigned int	height)

-{

-    region->extents.x1 = x;

-    region->extents.y1 = y;

-    region->extents.x2 = x + width;

-    region->extents.y2 = y + height;

-

-    if (!GOOD_RECT (&region->extents))

-    {

-        if (BAD_RECT (&region->extents))

-            _pixman_log_error (FUNC, "Invalid rectangle passed");

-        PREFIX (_init) (region);

-        return;

-    }

-

-    region->data = NULL;

-}

-

-PIXMAN_EXPORT void

-PREFIX (_init_with_extents) (region_type_t *region, box_type_t *extents)

-{

-    if (!GOOD_RECT (extents))

-    {

-        if (BAD_RECT (extents))

-            _pixman_log_error (FUNC, "Invalid rectangle passed");

-        PREFIX (_init) (region);

-        return;

-    }

-    region->extents = *extents;

-

-    region->data = NULL;

-}

-

-PIXMAN_EXPORT void

-PREFIX (_fini) (region_type_t *region)

-{

-    GOOD (region);

-    FREE_DATA (region);

-}

-

-PIXMAN_EXPORT int

-PREFIX (_n_rects) (region_type_t *region)

-{

-    return PIXREGION_NUMRECTS (region);

-}

-

-PIXMAN_EXPORT box_type_t *

-PREFIX (_rectangles) (region_type_t *region,

-                      int               *n_rects)

-{

-    if (n_rects)

-	*n_rects = PIXREGION_NUMRECTS (region);

-

-    return PIXREGION_RECTS (region);

-}

-

-static pixman_bool_t

-pixman_break (region_type_t *region)

-{

-    FREE_DATA (region);

-

-    region->extents = *pixman_region_empty_box;

-    region->data = pixman_broken_data;

-

-    return FALSE;

-}

-

-static pixman_bool_t

-pixman_rect_alloc (region_type_t * region,

-                   int             n)

-{

-    region_data_type_t *data;

-

-    if (!region->data)

-    {

-	n++;

-	region->data = alloc_data (n);

-

-	if (!region->data)

-	    return pixman_break (region);

-

-	region->data->numRects = 1;

-	*PIXREGION_BOXPTR (region) = region->extents;

-    }

-    else if (!region->data->size)

-    {

-	region->data = alloc_data (n);

-

-	if (!region->data)

-	    return pixman_break (region);

-

-	region->data->numRects = 0;

-    }

-    else

-    {

-	size_t data_size;

-

-	if (n == 1)

-	{

-	    n = region->data->numRects;

-	    if (n > 500) /* XXX pick numbers out of a hat */

-		n = 250;

-	}

-

-	n += region->data->numRects;

-	data_size = PIXREGION_SZOF (n);

-

-	if (!data_size)

-	{

-	    data = NULL;

-	}

-	else

-	{

-	    data = (region_data_type_t *)

-		realloc (region->data, PIXREGION_SZOF (n));

-	}

-	

-	if (!data)

-	    return pixman_break (region);

-	

-	region->data = data;

-    }

-    

-    region->data->size = n;

-

-    return TRUE;

-}

-

-PIXMAN_EXPORT pixman_bool_t

-PREFIX (_copy) (region_type_t *dst, region_type_t *src)

-{

-    GOOD (dst);

-    GOOD (src);

-

-    if (dst == src)

-	return TRUE;

-    

-    dst->extents = src->extents;

-

-    if (!src->data || !src->data->size)

-    {

-	FREE_DATA (dst);

-	dst->data = src->data;

-	return TRUE;

-    }

-    

-    if (!dst->data || (dst->data->size < src->data->numRects))

-    {

-	FREE_DATA (dst);

-

-	dst->data = alloc_data (src->data->numRects);

-

-	if (!dst->data)

-	    return pixman_break (dst);

-

-	dst->data->size = src->data->numRects;

-    }

-

-    dst->data->numRects = src->data->numRects;

-

-    memmove ((char *)PIXREGION_BOXPTR (dst), (char *)PIXREGION_BOXPTR (src),

-             dst->data->numRects * sizeof(box_type_t));

-

-    return TRUE;

-}

-

-/*======================================================================

- *	    Generic Region Operator

- *====================================================================*/

-

-/*-

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

- * pixman_coalesce --

- *	Attempt to merge the boxes in the current band with those in the

- *	previous one.  We are guaranteed that the current band extends to

- *      the end of the rects array.  Used only by pixman_op.

- *

- * Results:

- *	The new index for the previous band.

- *

- * Side Effects:

- *	If coalescing takes place:

- *	    - rectangles in the previous band will have their y2 fields

- *	      altered.

- *	    - region->data->numRects will be decreased.

- *

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

- */

-static inline int

-pixman_coalesce (region_type_t * region,      /* Region to coalesce		 */

-		 int             prev_start,  /* Index of start of previous band */

-		 int             cur_start)   /* Index of start of current band  */

-{

-    box_type_t *prev_box;       /* Current box in previous band	     */

-    box_type_t *cur_box;        /* Current box in current band       */

-    int numRects;               /* Number rectangles in both bands   */

-    int y2;                     /* Bottom of current band	     */

-

-    /*

-     * Figure out how many rectangles are in the band.

-     */

-    numRects = cur_start - prev_start;

-    critical_if_fail (numRects == region->data->numRects - cur_start);

-

-    if (!numRects) return cur_start;

-

-    /*

-     * The bands may only be coalesced if the bottom of the previous

-     * matches the top scanline of the current.

-     */

-    prev_box = PIXREGION_BOX (region, prev_start);

-    cur_box = PIXREGION_BOX (region, cur_start);

-    if (prev_box->y2 != cur_box->y1) return cur_start;

-

-    /*

-     * Make sure the bands have boxes in the same places. This

-     * assumes that boxes have been added in such a way that they

-     * cover the most area possible. I.e. two boxes in a band must

-     * have some horizontal space between them.

-     */

-    y2 = cur_box->y2;

-

-    do

-    {

-	if ((prev_box->x1 != cur_box->x1) || (prev_box->x2 != cur_box->x2))

-	    return (cur_start);

-	

-	prev_box++;

-	cur_box++;

-	numRects--;

-    }

-    while (numRects);

-

-    /*

-     * The bands may be merged, so set the bottom y of each box

-     * in the previous band to the bottom y of the current band.

-     */

-    numRects = cur_start - prev_start;

-    region->data->numRects -= numRects;

-

-    do

-    {

-	prev_box--;

-	prev_box->y2 = y2;

-	numRects--;

-    }

-    while (numRects);

-

-    return prev_start;

-}

-

-/* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */

-

-#define COALESCE(new_reg, prev_band, cur_band)                          \

-    do									\

-    {									\

-	if (cur_band - prev_band == new_reg->data->numRects - cur_band)	\

-	    prev_band = pixman_coalesce (new_reg, prev_band, cur_band);	\

-	else								\

-	    prev_band = cur_band;					\

-    } while (0)

-

-/*-

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

- * pixman_region_append_non_o --

- *	Handle a non-overlapping band for the union and subtract operations.

- *      Just adds the (top/bottom-clipped) rectangles into the region.

- *      Doesn't have to check for subsumption or anything.

- *

- * Results:

- *	None.

- *

- * Side Effects:

- *	region->data->numRects is incremented and the rectangles overwritten

- *	with the rectangles we're passed.

- *

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

- */

-static inline pixman_bool_t

-pixman_region_append_non_o (region_type_t * region,

-			    box_type_t *    r,

-			    box_type_t *    r_end,

-			    int             y1,

-			    int             y2)

-{

-    box_type_t *next_rect;

-    int new_rects;

-

-    new_rects = r_end - r;

-

-    critical_if_fail (y1 < y2);

-    critical_if_fail (new_rects != 0);

-

-    /* Make sure we have enough space for all rectangles to be added */

-    RECTALLOC (region, new_rects);

-    next_rect = PIXREGION_TOP (region);

-    region->data->numRects += new_rects;

-

-    do

-    {

-	critical_if_fail (r->x1 < r->x2);

-	ADDRECT (next_rect, r->x1, y1, r->x2, y2);

-	r++;

-    }

-    while (r != r_end);

-

-    return TRUE;

-}

-

-#define FIND_BAND(r, r_band_end, r_end, ry1)			     \

-    do								     \

-    {								     \

-	ry1 = r->y1;						     \

-	r_band_end = r + 1;					     \

-	while ((r_band_end != r_end) && (r_band_end->y1 == ry1)) {   \

-	    r_band_end++;					     \

-	}							     \

-    } while (0)

-

-#define APPEND_REGIONS(new_reg, r, r_end)				\

-    do									\

-    {									\

-	int new_rects;							\

-	if ((new_rects = r_end - r)) {					\

-	    RECTALLOC_BAIL (new_reg, new_rects, bail);			\

-	    memmove ((char *)PIXREGION_TOP (new_reg), (char *)r,	\

-		     new_rects * sizeof(box_type_t));			\

-	    new_reg->data->numRects += new_rects;			\

-	}								\

-    } while (0)

-

-/*-

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

- * pixman_op --

- *	Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,

- *	pixman_region_subtract, pixman_region_intersect....  Both regions MUST have at least one

- *      rectangle, and cannot be the same object.

- *

- * Results:

- *	TRUE if successful.

- *

- * Side Effects:

- *	The new region is overwritten.

- *	overlap set to TRUE if overlap_func ever returns TRUE.

- *

- * Notes:

- *	The idea behind this function is to view the two regions as sets.

- *	Together they cover a rectangle of area that this function divides

- *	into horizontal bands where points are covered only by one region

- *	or by both. For the first case, the non_overlap_func is called with

- *	each the band and the band's upper and lower extents. For the

- *	second, the overlap_func is called to process the entire band. It

- *	is responsible for clipping the rectangles in the band, though

- *	this function provides the boundaries.

- *	At the end of each band, the new region is coalesced, if possible,

- *	to reduce the number of rectangles in the region.

- *

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

- */

-

-typedef pixman_bool_t (*overlap_proc_ptr) (region_type_t *region,

-					   box_type_t *   r1,

-					   box_type_t *   r1_end,

-					   box_type_t *   r2,

-					   box_type_t *   r2_end,

-					   int            y1,

-					   int            y2,

-					   int *          overlap);

-

-static pixman_bool_t

-pixman_op (region_type_t *  new_reg,               /* Place to store result	    */

-	   region_type_t *  reg1,                  /* First region in operation     */

-	   region_type_t *  reg2,                  /* 2d region in operation        */

-	   overlap_proc_ptr overlap_func,          /* Function to call for over-

-						    * lapping bands		    */

-	   int              append_non1,           /* Append non-overlapping bands  

-						    * in region 1 ?

-						    */

-	   int              append_non2,           /* Append non-overlapping bands

-						    * in region 2 ?

-						    */

-	   int *            overlap)

-{

-    box_type_t *r1;                 /* Pointer into first region     */

-    box_type_t *r2;                 /* Pointer into 2d region	     */

-    box_type_t *r1_end;             /* End of 1st region	     */

-    box_type_t *r2_end;             /* End of 2d region		     */

-    int ybot;                       /* Bottom of intersection	     */

-    int ytop;                       /* Top of intersection	     */

-    region_data_type_t *old_data;   /* Old data for new_reg	     */

-    int prev_band;                  /* Index of start of

-				     * previous band in new_reg       */

-    int cur_band;                   /* Index of start of current

-				     * band in new_reg		     */

-    box_type_t * r1_band_end;       /* End of current band in r1     */

-    box_type_t * r2_band_end;       /* End of current band in r2     */

-    int top;                        /* Top of non-overlapping band   */

-    int bot;                        /* Bottom of non-overlapping band*/

-    int r1y1;                       /* Temps for r1->y1 and r2->y1   */

-    int r2y1;

-    int new_size;

-    int numRects;

-

-    /*

-     * Break any region computed from a broken region

-     */

-    if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))

-	return pixman_break (new_reg);

-

-    /*

-     * Initialization:

-     *	set r1, r2, r1_end and r2_end appropriately, save the rectangles

-     * of the destination region until the end in case it's one of

-     * the two source regions, then mark the "new" region empty, allocating

-     * another array of rectangles for it to use.

-     */

-

-    r1 = PIXREGION_RECTS (reg1);

-    new_size = PIXREGION_NUMRECTS (reg1);

-    r1_end = r1 + new_size;

-

-    numRects = PIXREGION_NUMRECTS (reg2);

-    r2 = PIXREGION_RECTS (reg2);

-    r2_end = r2 + numRects;

-    

-    critical_if_fail (r1 != r1_end);

-    critical_if_fail (r2 != r2_end);

-

-    old_data = (region_data_type_t *)NULL;

-

-    if (((new_reg == reg1) && (new_size > 1)) ||

-        ((new_reg == reg2) && (numRects > 1)))

-    {

-        old_data = new_reg->data;

-        new_reg->data = pixman_region_empty_data;

-    }

-

-    /* guess at new size */

-    if (numRects > new_size)

-	new_size = numRects;

-

-    new_size <<= 1;

-

-    if (!new_reg->data)

-	new_reg->data = pixman_region_empty_data;

-    else if (new_reg->data->size)

-	new_reg->data->numRects = 0;

-

-    if (new_size > new_reg->data->size)

-    {

-        if (!pixman_rect_alloc (new_reg, new_size))

-        {

-            if (old_data)

-		free (old_data);

-            return FALSE;

-	}

-    }

-

-    /*

-     * Initialize ybot.

-     * In the upcoming loop, ybot and ytop serve different functions depending

-     * on whether the band being handled is an overlapping or non-overlapping

-     * band.

-     *  In the case of a non-overlapping band (only one of the regions

-     * has points in the band), ybot is the bottom of the most recent

-     * intersection and thus clips the top of the rectangles in that band.

-     * ytop is the top of the next intersection between the two regions and

-     * serves to clip the bottom of the rectangles in the current band.

-     *	For an overlapping band (where the two regions intersect), ytop clips

-     * the top of the rectangles of both regions and ybot clips the bottoms.

-     */

-

-    ybot = MIN (r1->y1, r2->y1);

-

-    /*

-     * prev_band serves to mark the start of the previous band so rectangles

-     * can be coalesced into larger rectangles. qv. pixman_coalesce, above.

-     * In the beginning, there is no previous band, so prev_band == cur_band

-     * (cur_band is set later on, of course, but the first band will always

-     * start at index 0). prev_band and cur_band must be indices because of

-     * the possible expansion, and resultant moving, of the new region's

-     * array of rectangles.

-     */

-    prev_band = 0;

-

-    do

-    {

-        /*

-	 * This algorithm proceeds one source-band (as opposed to a

-	 * destination band, which is determined by where the two regions

-	 * intersect) at a time. r1_band_end and r2_band_end serve to mark the

-	 * rectangle after the last one in the current band for their

-	 * respective regions.

-	 */

-        critical_if_fail (r1 != r1_end);

-        critical_if_fail (r2 != r2_end);

-

-        FIND_BAND (r1, r1_band_end, r1_end, r1y1);

-        FIND_BAND (r2, r2_band_end, r2_end, r2y1);

-

-        /*

-	 * First handle the band that doesn't intersect, if any.

-	 *

-	 * Note that attention is restricted to one band in the

-	 * non-intersecting region at once, so if a region has n

-	 * bands between the current position and the next place it overlaps

-	 * the other, this entire loop will be passed through n times.

-	 */

-        if (r1y1 < r2y1)

-        {

-            if (append_non1)

-            {

-                top = MAX (r1y1, ybot);

-                bot = MIN (r1->y2, r2y1);

-                if (top != bot)

-                {

-                    cur_band = new_reg->data->numRects;

-                    if (!pixman_region_append_non_o (new_reg, r1, r1_band_end, top, bot))

-			goto bail;

-                    COALESCE (new_reg, prev_band, cur_band);

-		}

-	    }

-            ytop = r2y1;

-	}

-        else if (r2y1 < r1y1)

-        {

-            if (append_non2)

-            {

-                top = MAX (r2y1, ybot);

-                bot = MIN (r2->y2, r1y1);

-		

-                if (top != bot)

-                {

-                    cur_band = new_reg->data->numRects;

-

-                    if (!pixman_region_append_non_o (new_reg, r2, r2_band_end, top, bot))

-			goto bail;

-

-                    COALESCE (new_reg, prev_band, cur_band);

-		}

-	    }

-            ytop = r1y1;

-	}

-        else

-        {

-            ytop = r1y1;

-	}

-

-        /*

-	 * Now see if we've hit an intersecting band. The two bands only

-	 * intersect if ybot > ytop

-	 */

-        ybot = MIN (r1->y2, r2->y2);

-        if (ybot > ytop)

-        {

-            cur_band = new_reg->data->numRects;

-

-            if (!(*overlap_func)(new_reg,

-                                 r1, r1_band_end,

-                                 r2, r2_band_end,

-                                 ytop, ybot,

-                                 overlap))

-	    {

-		goto bail;

-	    }

-	    

-            COALESCE (new_reg, prev_band, cur_band);

-	}

-

-        /*

-	 * If we've finished with a band (y2 == ybot) we skip forward

-	 * in the region to the next band.

-	 */

-        if (r1->y2 == ybot)

-	    r1 = r1_band_end;

-

-        if (r2->y2 == ybot)

-	    r2 = r2_band_end;

-

-    }

-    while (r1 != r1_end && r2 != r2_end);

-

-    /*

-     * Deal with whichever region (if any) still has rectangles left.

-     *

-     * We only need to worry about banding and coalescing for the very first

-     * band left.  After that, we can just group all remaining boxes,

-     * regardless of how many bands, into one final append to the list.

-     */

-

-    if ((r1 != r1_end) && append_non1)

-    {

-        /* Do first non_overlap1Func call, which may be able to coalesce */

-        FIND_BAND (r1, r1_band_end, r1_end, r1y1);

-	

-        cur_band = new_reg->data->numRects;

-	

-        if (!pixman_region_append_non_o (new_reg,

-                                         r1, r1_band_end,

-                                         MAX (r1y1, ybot), r1->y2))

-	{

-	    goto bail;

-	}

-	

-        COALESCE (new_reg, prev_band, cur_band);

-

-        /* Just append the rest of the boxes  */

-        APPEND_REGIONS (new_reg, r1_band_end, r1_end);

-    }

-    else if ((r2 != r2_end) && append_non2)

-    {

-        /* Do first non_overlap2Func call, which may be able to coalesce */

-        FIND_BAND (r2, r2_band_end, r2_end, r2y1);

-

-	cur_band = new_reg->data->numRects;

-

-        if (!pixman_region_append_non_o (new_reg,

-                                         r2, r2_band_end,

-                                         MAX (r2y1, ybot), r2->y2))

-	{

-	    goto bail;

-	}

-

-        COALESCE (new_reg, prev_band, cur_band);

-

-        /* Append rest of boxes */

-        APPEND_REGIONS (new_reg, r2_band_end, r2_end);

-    }

-

-    if (old_data)

-	free (old_data);

-

-    if (!(numRects = new_reg->data->numRects))

-    {

-        FREE_DATA (new_reg);

-        new_reg->data = pixman_region_empty_data;

-    }

-    else if (numRects == 1)

-    {

-        new_reg->extents = *PIXREGION_BOXPTR (new_reg);

-        FREE_DATA (new_reg);

-        new_reg->data = (region_data_type_t *)NULL;

-    }

-    else

-    {

-        DOWNSIZE (new_reg, numRects);

-    }

-

-    return TRUE;

-

-bail:

-    if (old_data)

-	free (old_data);

-

-    return pixman_break (new_reg);

-}

-

-/*-

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

- * pixman_set_extents --

- *	Reset the extents of a region to what they should be. Called by

- *	pixman_region_subtract and pixman_region_intersect as they can't

- *      figure it out along the way or do so easily, as pixman_region_union can.

- *

- * Results:

- *	None.

- *

- * Side Effects:

- *	The region's 'extents' structure is overwritten.

- *

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

- */

-static void

-pixman_set_extents (region_type_t *region)

-{

-    box_type_t *box, *box_end;

-

-    if (!region->data)

-	return;

-

-    if (!region->data->size)

-    {

-        region->extents.x2 = region->extents.x1;

-        region->extents.y2 = region->extents.y1;

-        return;

-    }

-

-    box = PIXREGION_BOXPTR (region);

-    box_end = PIXREGION_END (region);

-

-    /*

-     * Since box is the first rectangle in the region, it must have the

-     * smallest y1 and since box_end is the last rectangle in the region,

-     * it must have the largest y2, because of banding. Initialize x1 and

-     * x2 from  box and box_end, resp., as good things to initialize them

-     * to...

-     */

-    region->extents.x1 = box->x1;

-    region->extents.y1 = box->y1;

-    region->extents.x2 = box_end->x2;

-    region->extents.y2 = box_end->y2;

-

-    critical_if_fail (region->extents.y1 < region->extents.y2);

-

-    while (box <= box_end)

-    {

-        if (box->x1 < region->extents.x1)

-	    region->extents.x1 = box->x1;

-        if (box->x2 > region->extents.x2)

-	    region->extents.x2 = box->x2;

-        box++;

-    }

-

-    critical_if_fail (region->extents.x1 < region->extents.x2);

-}

-

-/*======================================================================

- *	    Region Intersection

- *====================================================================*/

-/*-

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

- * pixman_region_intersect_o --

- *	Handle an overlapping band for pixman_region_intersect.

- *

- * Results:

- *	TRUE if successful.

- *

- * Side Effects:

- *	Rectangles may be added to the region.

- *

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

- */

-/*ARGSUSED*/

-static pixman_bool_t

-pixman_region_intersect_o (region_type_t *region,

-                           box_type_t *   r1,

-                           box_type_t *   r1_end,

-                           box_type_t *   r2,

-                           box_type_t *   r2_end,

-                           int            y1,

-                           int            y2,

-                           int *          overlap)

-{

-    int x1;

-    int x2;

-    box_type_t *        next_rect;

-

-    next_rect = PIXREGION_TOP (region);

-

-    critical_if_fail (y1 < y2);

-    critical_if_fail (r1 != r1_end && r2 != r2_end);

-

-    do

-    {

-        x1 = MAX (r1->x1, r2->x1);

-        x2 = MIN (r1->x2, r2->x2);

-

-        /*

-	 * If there's any overlap between the two rectangles, add that

-	 * overlap to the new region.

-	 */

-        if (x1 < x2)

-	    NEWRECT (region, next_rect, x1, y1, x2, y2);

-

-        /*

-	 * Advance the pointer(s) with the leftmost right side, since the next

-	 * rectangle on that list may still overlap the other region's

-	 * current rectangle.

-	 */

-        if (r1->x2 == x2)

-        {

-            r1++;

-	}

-        if (r2->x2 == x2)

-        {

-            r2++;

-	}

-    }

-    while ((r1 != r1_end) && (r2 != r2_end));

-

-    return TRUE;

-}

-

-PIXMAN_EXPORT pixman_bool_t

-PREFIX (_intersect) (region_type_t *     new_reg,

-                     region_type_t *        reg1,

-                     region_type_t *        reg2)

-{

-    GOOD (reg1);

-    GOOD (reg2);

-    GOOD (new_reg);

-

-    /* check for trivial reject */

-    if (PIXREGION_NIL (reg1) || PIXREGION_NIL (reg2) ||

-        !EXTENTCHECK (&reg1->extents, &reg2->extents))

-    {

-        /* Covers about 20% of all cases */

-        FREE_DATA (new_reg);

-        new_reg->extents.x2 = new_reg->extents.x1;

-        new_reg->extents.y2 = new_reg->extents.y1;

-        if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))

-        {

-            new_reg->data = pixman_broken_data;

-            return FALSE;

-	}

-        else

-	{

-	    new_reg->data = pixman_region_empty_data;

-	}

-    }

-    else if (!reg1->data && !reg2->data)

-    {

-        /* Covers about 80% of cases that aren't trivially rejected */

-        new_reg->extents.x1 = MAX (reg1->extents.x1, reg2->extents.x1);

-        new_reg->extents.y1 = MAX (reg1->extents.y1, reg2->extents.y1);

-        new_reg->extents.x2 = MIN (reg1->extents.x2, reg2->extents.x2);

-        new_reg->extents.y2 = MIN (reg1->extents.y2, reg2->extents.y2);

-

-        FREE_DATA (new_reg);

-

-	new_reg->data = (region_data_type_t *)NULL;

-    }

-    else if (!reg2->data && SUBSUMES (&reg2->extents, &reg1->extents))

-    {

-        return PREFIX (_copy) (new_reg, reg1);

-    }

-    else if (!reg1->data && SUBSUMES (&reg1->extents, &reg2->extents))

-    {

-        return PREFIX (_copy) (new_reg, reg2);

-    }

-    else if (reg1 == reg2)

-    {

-        return PREFIX (_copy) (new_reg, reg1);

-    }

-    else

-    {

-        /* General purpose intersection */

-        int overlap; /* result ignored */

-

-        if (!pixman_op (new_reg, reg1, reg2, pixman_region_intersect_o, FALSE, FALSE,

-                        &overlap))

-	{

-	    return FALSE;

-	}

-	

-        pixman_set_extents (new_reg);

-    }

-

-    GOOD (new_reg);

-    return(TRUE);

-}

-

-#define MERGERECT(r)							\

-    do									\

-    {									\

-        if (r->x1 <= x2)						\

-	{								\

-            /* Merge with current rectangle */				\

-            if (r->x1 < x2)						\

-		*overlap = TRUE;					\

-									\

-            if (x2 < r->x2)						\

-		x2 = r->x2;						\

-	}								\

-	else								\

-	{								\

-            /* Add current rectangle, start new one */			\

-            NEWRECT (region, next_rect, x1, y1, x2, y2);		\

-            x1 = r->x1;							\

-            x2 = r->x2;							\

-	}								\

-        r++;								\

-    } while (0)

-

-/*======================================================================

- *	    Region Union

- *====================================================================*/

-

-/*-

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

- * pixman_region_union_o --

- *	Handle an overlapping band for the union operation. Picks the

- *	left-most rectangle each time and merges it into the region.

- *

- * Results:

- *	TRUE if successful.

- *

- * Side Effects:

- *	region is overwritten.

- *	overlap is set to TRUE if any boxes overlap.

- *

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

- */

-static pixman_bool_t

-pixman_region_union_o (region_type_t *region,

-		       box_type_t *   r1,

-		       box_type_t *   r1_end,

-		       box_type_t *   r2,

-		       box_type_t *   r2_end,

-		       int            y1,

-		       int            y2,

-		       int *          overlap)

-{

-    box_type_t *next_rect;

-    int x1;            /* left and right side of current union */

-    int x2;

-

-    critical_if_fail (y1 < y2);

-    critical_if_fail (r1 != r1_end && r2 != r2_end);

-

-    next_rect = PIXREGION_TOP (region);

-

-    /* Start off current rectangle */

-    if (r1->x1 < r2->x1)

-    {

-        x1 = r1->x1;

-        x2 = r1->x2;

-        r1++;

-    }

-    else

-    {

-        x1 = r2->x1;

-        x2 = r2->x2;

-        r2++;

-    }

-    while (r1 != r1_end && r2 != r2_end)

-    {

-        if (r1->x1 < r2->x1)

-	    MERGERECT (r1);

-	else

-	    MERGERECT (r2);

-    }

-

-    /* Finish off whoever (if any) is left */

-    if (r1 != r1_end)

-    {

-        do

-        {

-            MERGERECT (r1);

-	}

-        while (r1 != r1_end);

-    }

-    else if (r2 != r2_end)

-    {

-        do

-        {

-            MERGERECT (r2);

-	}

-        while (r2 != r2_end);

-    }

-

-    /* Add current rectangle */

-    NEWRECT (region, next_rect, x1, y1, x2, y2);

-

-    return TRUE;

-}

-

-PIXMAN_EXPORT pixman_bool_t

-PREFIX(_intersect_rect) (region_type_t *dest,

-			 region_type_t *source,

-			 int x, int y,

-			 unsigned int width,

-			 unsigned int height)

-{

-    region_type_t region;

-

-    region.data = NULL;

-    region.extents.x1 = x;

-    region.extents.y1 = y;

-    region.extents.x2 = x + width;

-    region.extents.y2 = y + height;

-

-    return PREFIX(_intersect) (dest, source, &region);

-}

-

-/* Convenience function for performing union of region with a

- * single rectangle

- */

-PIXMAN_EXPORT pixman_bool_t

-PREFIX (_union_rect) (region_type_t *dest,

-                      region_type_t *source,

-                      int            x,

-		      int            y,

-                      unsigned int   width,

-		      unsigned int   height)

-{

-    region_type_t region;

-

-    region.extents.x1 = x;

-    region.extents.y1 = y;

-    region.extents.x2 = x + width;

-    region.extents.y2 = y + height;

-

-    if (!GOOD_RECT (&region.extents))

-    {

-        if (BAD_RECT (&region.extents))

-            _pixman_log_error (FUNC, "Invalid rectangle passed");

-	return PREFIX (_copy) (dest, source);

-    }

-

-    region.data = NULL;

-

-    return PREFIX (_union) (dest, source, &region);

-}

-

-PIXMAN_EXPORT pixman_bool_t

-PREFIX (_union) (region_type_t *new_reg,

-                 region_type_t *reg1,

-                 region_type_t *reg2)

-{

-    int overlap; /* result ignored */

-

-    /* Return TRUE if some overlap

-     * between reg1, reg2

-     */

-    GOOD (reg1);

-    GOOD (reg2);

-    GOOD (new_reg);

-

-    /*  checks all the simple cases */

-

-    /*

-     * Region 1 and 2 are the same

-     */

-    if (reg1 == reg2)

-        return PREFIX (_copy) (new_reg, reg1);

-

-    /*

-     * Region 1 is empty

-     */

-    if (PIXREGION_NIL (reg1))

-    {

-        if (PIXREGION_NAR (reg1))

-	    return pixman_break (new_reg);

-

-        if (new_reg != reg2)

-	    return PREFIX (_copy) (new_reg, reg2);

-

-	return TRUE;

-    }

-

-    /*

-     * Region 2 is empty

-     */

-    if (PIXREGION_NIL (reg2))

-    {

-        if (PIXREGION_NAR (reg2))

-	    return pixman_break (new_reg);

-

-	if (new_reg != reg1)

-	    return PREFIX (_copy) (new_reg, reg1);

-

-	return TRUE;

-    }

-

-    /*

-     * Region 1 completely subsumes region 2

-     */

-    if (!reg1->data && SUBSUMES (&reg1->extents, &reg2->extents))

-    {

-        if (new_reg != reg1)

-	    return PREFIX (_copy) (new_reg, reg1);

-

-	return TRUE;

-    }

-

-    /*

-     * Region 2 completely subsumes region 1

-     */

-    if (!reg2->data && SUBSUMES (&reg2->extents, &reg1->extents))

-    {

-        if (new_reg != reg2)

-	    return PREFIX (_copy) (new_reg, reg2);

-

-	return TRUE;

-    }

-

-    if (!pixman_op (new_reg, reg1, reg2, pixman_region_union_o, TRUE, TRUE, &overlap))

-	return FALSE;

-

-    new_reg->extents.x1 = MIN (reg1->extents.x1, reg2->extents.x1);

-    new_reg->extents.y1 = MIN (reg1->extents.y1, reg2->extents.y1);

-    new_reg->extents.x2 = MAX (reg1->extents.x2, reg2->extents.x2);

-    new_reg->extents.y2 = MAX (reg1->extents.y2, reg2->extents.y2);

-    

-    GOOD (new_reg);

-

-    return TRUE;

-}

-

-/*======================================================================

- *	    Batch Rectangle Union

- *====================================================================*/

-

-#define EXCHANGE_RECTS(a, b)	\

-    {                           \

-        box_type_t t;		\

-        t = rects[a];           \

-        rects[a] = rects[b];    \

-        rects[b] = t;           \

-    }

-

-static void

-quick_sort_rects (

-    box_type_t rects[],

-    int        numRects)

-{

-    int y1;

-    int x1;

-    int i, j;

-    box_type_t *r;

-

-    /* Always called with numRects > 1 */

-

-    do

-    {

-        if (numRects == 2)

-        {

-            if (rects[0].y1 > rects[1].y1 ||

-                (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))

-	    {

-		EXCHANGE_RECTS (0, 1);

-	    }

-

-            return;

-	}

-

-        /* Choose partition element, stick in location 0 */

-        EXCHANGE_RECTS (0, numRects >> 1);

-        y1 = rects[0].y1;

-        x1 = rects[0].x1;

-

-        /* Partition array */

-        i = 0;

-        j = numRects;

-

-        do

-        {

-            r = &(rects[i]);

-            do

-            {

-                r++;

-                i++;

-	    }

-

-            while (i != numRects && (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)))

-		;

-

-	    r = &(rects[j]);

-            do

-            {

-                r--;

-                j--;

-	    }

-            while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));

-	    

-            if (i < j)

-		EXCHANGE_RECTS (i, j);

-	}

-        while (i < j);

-

-        /* Move partition element back to middle */

-        EXCHANGE_RECTS (0, j);

-

-        /* Recurse */

-        if (numRects - j - 1 > 1)

-	    quick_sort_rects (&rects[j + 1], numRects - j - 1);

-

-        numRects = j;

-    }

-    while (numRects > 1);

-}

-

-/*-

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

- * pixman_region_validate --

- *

- *      Take a ``region'' which is a non-y-x-banded random collection of

- *      rectangles, and compute a nice region which is the union of all the

- *      rectangles.

- *

- * Results:

- *	TRUE if successful.

- *

- * Side Effects:

- *      The passed-in ``region'' may be modified.

- *	overlap set to TRUE if any retangles overlapped,

- *      else FALSE;

- *

- * Strategy:

- *      Step 1. Sort the rectangles into ascending order with primary key y1

- *		and secondary key x1.

- *

- *      Step 2. Split the rectangles into the minimum number of proper y-x

- *		banded regions.  This may require horizontally merging

- *		rectangles, and vertically coalescing bands.  With any luck,

- *		this step in an identity transformation (ala the Box widget),

- *		or a coalescing into 1 box (ala Menus).

- *

- *	Step 3. Merge the separate regions down to a single region by calling

- *		pixman_region_union.  Maximize the work each pixman_region_union call does by using

- *		a binary merge.

- *

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

- */

-

-static pixman_bool_t

-validate (region_type_t * badreg,

-          int *           overlap)

-{

-    /* Descriptor for regions under construction  in Step 2. */

-    typedef struct

-    {

-        region_type_t reg;

-        int prev_band;

-        int cur_band;

-    } region_info_t;

-

-    region_info_t stack_regions[64];

-

-    int numRects;                   /* Original numRects for badreg	    */

-    region_info_t *ri;              /* Array of current regions		    */

-    int num_ri;                     /* Number of entries used in ri	    */

-    int size_ri;                    /* Number of entries available in ri    */

-    int i;                          /* Index into rects			    */

-    int j;                          /* Index into ri			    */

-    region_info_t *rit;             /* &ri[j]				    */

-    region_type_t *reg;             /* ri[j].reg			    */

-    box_type_t *box;                /* Current box in rects		    */

-    box_type_t *ri_box;             /* Last box in ri[j].reg		    */

-    region_type_t *hreg;            /* ri[j_half].reg			    */

-    pixman_bool_t ret = TRUE;

-

-    *overlap = FALSE;

-    if (!badreg->data)

-    {

-        GOOD (badreg);

-        return TRUE;

-    }

-    

-    numRects = badreg->data->numRects;

-    if (!numRects)

-    {

-        if (PIXREGION_NAR (badreg))

-	    return FALSE;

-        GOOD (badreg);

-        return TRUE;

-    }

-    

-    if (badreg->extents.x1 < badreg->extents.x2)

-    {

-        if ((numRects) == 1)

-        {

-            FREE_DATA (badreg);

-            badreg->data = (region_data_type_t *) NULL;

-	}

-        else

-        {

-            DOWNSIZE (badreg, numRects);

-	}

-

-        GOOD (badreg);

-

-	return TRUE;

-    }

-

-    /* Step 1: Sort the rects array into ascending (y1, x1) order */

-    quick_sort_rects (PIXREGION_BOXPTR (badreg), numRects);

-

-    /* Step 2: Scatter the sorted array into the minimum number of regions */

-

-    /* Set up the first region to be the first rectangle in badreg */

-    /* Note that step 2 code will never overflow the ri[0].reg rects array */

-    ri = stack_regions;

-    size_ri = sizeof (stack_regions) / sizeof (stack_regions[0]);

-    num_ri = 1;

-    ri[0].prev_band = 0;

-    ri[0].cur_band = 0;

-    ri[0].reg = *badreg;

-    box = PIXREGION_BOXPTR (&ri[0].reg);

-    ri[0].reg.extents = *box;

-    ri[0].reg.data->numRects = 1;

-    badreg->extents = *pixman_region_empty_box;

-    badreg->data = pixman_region_empty_data;

-

-    /* Now scatter rectangles into the minimum set of valid regions.  If the

-     * next rectangle to be added to a region would force an existing rectangle

-     * in the region to be split up in order to maintain y-x banding, just

-     * forget it.  Try the next region.  If it doesn't fit cleanly into any

-     * region, make a new one.

-     */

-

-    for (i = numRects; --i > 0;)

-    {

-        box++;

-        /* Look for a region to append box to */

-        for (j = num_ri, rit = ri; --j >= 0; rit++)

-        {

-            reg = &rit->reg;

-            ri_box = PIXREGION_END (reg);

-

-            if (box->y1 == ri_box->y1 && box->y2 == ri_box->y2)

-            {

-                /* box is in same band as ri_box.  Merge or append it */

-                if (box->x1 <= ri_box->x2)

-                {

-                    /* Merge it with ri_box */

-                    if (box->x1 < ri_box->x2)

-			*overlap = TRUE;

-

-                    if (box->x2 > ri_box->x2)

-			ri_box->x2 = box->x2;

-		}

-                else

-                {

-                    RECTALLOC_BAIL (reg, 1, bail);

-                    *PIXREGION_TOP (reg) = *box;

-                    reg->data->numRects++;

-		}

-		

-                goto next_rect;   /* So sue me */

-	    }

-            else if (box->y1 >= ri_box->y2)

-            {

-                /* Put box into new band */

-                if (reg->extents.x2 < ri_box->x2)

-		    reg->extents.x2 = ri_box->x2;

-		

-                if (reg->extents.x1 > box->x1)

-		    reg->extents.x1 = box->x1;

-		

-                COALESCE (reg, rit->prev_band, rit->cur_band);

-                rit->cur_band = reg->data->numRects;

-                RECTALLOC_BAIL (reg, 1, bail);

-                *PIXREGION_TOP (reg) = *box;

-                reg->data->numRects++;

-

-                goto next_rect;

-	    }

-            /* Well, this region was inappropriate.  Try the next one. */

-	} /* for j */

-

-        /* Uh-oh.  No regions were appropriate.  Create a new one. */

-        if (size_ri == num_ri)

-        {

-            size_t data_size;

-

-            /* Oops, allocate space for new region information */

-            size_ri <<= 1;

-

-            data_size = size_ri * sizeof(region_info_t);

-            if (data_size / size_ri != sizeof(region_info_t))

-		goto bail;

-

-            if (ri == stack_regions)

-            {

-                rit = malloc (data_size);

-                if (!rit)

-		    goto bail;

-                memcpy (rit, ri, num_ri * sizeof (region_info_t));

-	    }

-            else

-            {

-                rit = (region_info_t *) realloc (ri, data_size);

-                if (!rit)

-		    goto bail;

-	    }

-            ri = rit;

-            rit = &ri[num_ri];

-	}

-        num_ri++;

-        rit->prev_band = 0;

-        rit->cur_band = 0;

-        rit->reg.extents = *box;

-        rit->reg.data = (region_data_type_t *)NULL;

-

-	/* MUST force allocation */

-        if (!pixman_rect_alloc (&rit->reg, (i + num_ri) / num_ri))

-	    goto bail;

-	

-    next_rect: ;

-    } /* for i */

-

-    /* Make a final pass over each region in order to COALESCE and set

-     * extents.x2 and extents.y2

-     */

-    for (j = num_ri, rit = ri; --j >= 0; rit++)

-    {

-        reg = &rit->reg;

-        ri_box = PIXREGION_END (reg);

-        reg->extents.y2 = ri_box->y2;

-

-        if (reg->extents.x2 < ri_box->x2)

-	    reg->extents.x2 = ri_box->x2;

-	

-        COALESCE (reg, rit->prev_band, rit->cur_band);

-

-	if (reg->data->numRects == 1) /* keep unions happy below */

-        {

-            FREE_DATA (reg);

-            reg->data = (region_data_type_t *)NULL;

-	}

-    }

-

-    /* Step 3: Union all regions into a single region */

-    while (num_ri > 1)

-    {

-        int half = num_ri / 2;

-        for (j = num_ri & 1; j < (half + (num_ri & 1)); j++)

-        {

-            reg = &ri[j].reg;

-            hreg = &ri[j + half].reg;

-

-            if (!pixman_op (reg, reg, hreg, pixman_region_union_o, TRUE, TRUE, overlap))

-		ret = FALSE;

-

-            if (hreg->extents.x1 < reg->extents.x1)

-		reg->extents.x1 = hreg->extents.x1;

-

-            if (hreg->extents.y1 < reg->extents.y1)

-		reg->extents.y1 = hreg->extents.y1;

-

-            if (hreg->extents.x2 > reg->extents.x2)

-		reg->extents.x2 = hreg->extents.x2;

-

-            if (hreg->extents.y2 > reg->extents.y2)

-		reg->extents.y2 = hreg->extents.y2;

-

-            FREE_DATA (hreg);

-	}

-

-        num_ri -= half;

-

-	if (!ret)

-	    goto bail;

-    }

-

-    *badreg = ri[0].reg;

-

-    if (ri != stack_regions)

-	free (ri);

-

-    GOOD (badreg);

-    return ret;

-

-bail:

-    for (i = 0; i < num_ri; i++)

-	FREE_DATA (&ri[i].reg);

-

-    if (ri != stack_regions)

-	free (ri);

-

-    return pixman_break (badreg);

-}

-

-/*======================================================================

- *                Region Subtraction

- *====================================================================*/

-

-/*-

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

- * pixman_region_subtract_o --

- *	Overlapping band subtraction. x1 is the left-most point not yet

- *	checked.

- *

- * Results:

- *	TRUE if successful.

- *

- * Side Effects:

- *	region may have rectangles added to it.

- *

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

- */

-/*ARGSUSED*/

-static pixman_bool_t

-pixman_region_subtract_o (region_type_t * region,

-			  box_type_t *    r1,

-			  box_type_t *    r1_end,

-			  box_type_t *    r2,

-			  box_type_t *    r2_end,

-			  int             y1,

-			  int             y2,

-			  int *           overlap)

-{

-    box_type_t *        next_rect;

-    int x1;

-

-    x1 = r1->x1;

-

-    critical_if_fail (y1 < y2);

-    critical_if_fail (r1 != r1_end && r2 != r2_end);

-

-    next_rect = PIXREGION_TOP (region);

-

-    do

-    {

-        if (r2->x2 <= x1)

-        {

-            /*

-	     * Subtrahend entirely to left of minuend: go to next subtrahend.

-	     */

-            r2++;

-	}

-        else if (r2->x1 <= x1)

-        {

-            /*

-	     * Subtrahend preceeds minuend: nuke left edge of minuend.

-	     */

-            x1 = r2->x2;

-            if (x1 >= r1->x2)

-            {

-                /*

-		 * Minuend completely covered: advance to next minuend and

-		 * reset left fence to edge of new minuend.

-		 */

-                r1++;

-                if (r1 != r1_end)

-		    x1 = r1->x1;

-	    }

-            else

-            {

-                /*

-		 * Subtrahend now used up since it doesn't extend beyond

-		 * minuend

-		 */

-                r2++;

-	    }

-	}

-        else if (r2->x1 < r1->x2)

-        {

-            /*

-	     * Left part of subtrahend covers part of minuend: add uncovered

-	     * part of minuend to region and skip to next subtrahend.

-	     */

-            critical_if_fail (x1 < r2->x1);

-            NEWRECT (region, next_rect, x1, y1, r2->x1, y2);

-

-            x1 = r2->x2;

-            if (x1 >= r1->x2)

-            {

-                /*

-		 * Minuend used up: advance to new...

-		 */

-                r1++;

-                if (r1 != r1_end)

-		    x1 = r1->x1;

-	    }

-            else

-            {

-                /*

-		 * Subtrahend used up

-		 */

-                r2++;

-	    }

-	}

-        else

-        {

-            /*

-	     * Minuend used up: add any remaining piece before advancing.

-	     */

-            if (r1->x2 > x1)

-		NEWRECT (region, next_rect, x1, y1, r1->x2, y2);

-

-            r1++;

-

-	    if (r1 != r1_end)

-		x1 = r1->x1;

-	}

-    }

-    while ((r1 != r1_end) && (r2 != r2_end));

-

-    /*

-     * Add remaining minuend rectangles to region.

-     */

-    while (r1 != r1_end)

-    {

-        critical_if_fail (x1 < r1->x2);

-

-        NEWRECT (region, next_rect, x1, y1, r1->x2, y2);

-

-        r1++;

-        if (r1 != r1_end)

-	    x1 = r1->x1;

-    }

-    return TRUE;

-}

-

-/*-

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

- * pixman_region_subtract --

- *	Subtract reg_s from reg_m and leave the result in reg_d.

- *	S stands for subtrahend, M for minuend and D for difference.

- *

- * Results:

- *	TRUE if successful.

- *

- * Side Effects:

- *	reg_d is overwritten.

- *

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

- */

-PIXMAN_EXPORT pixman_bool_t

-PREFIX (_subtract) (region_type_t *reg_d,

-                    region_type_t *reg_m,

-                    region_type_t *reg_s)

-{

-    int overlap; /* result ignored */

-

-    GOOD (reg_m);

-    GOOD (reg_s);

-    GOOD (reg_d);

-    

-    /* check for trivial rejects */

-    if (PIXREGION_NIL (reg_m) || PIXREGION_NIL (reg_s) ||

-        !EXTENTCHECK (&reg_m->extents, &reg_s->extents))

-    {

-        if (PIXREGION_NAR (reg_s))

-	    return pixman_break (reg_d);

-	

-        return PREFIX (_copy) (reg_d, reg_m);

-    }

-    else if (reg_m == reg_s)

-    {

-        FREE_DATA (reg_d);

-        reg_d->extents.x2 = reg_d->extents.x1;

-        reg_d->extents.y2 = reg_d->extents.y1;

-        reg_d->data = pixman_region_empty_data;

-

-        return TRUE;

-    }

-

-    /* Add those rectangles in region 1 that aren't in region 2,

-       do yucky substraction for overlaps, and

-       just throw away rectangles in region 2 that aren't in region 1 */

-    if (!pixman_op (reg_d, reg_m, reg_s, pixman_region_subtract_o, TRUE, FALSE, &overlap))

-	return FALSE;

-

-    /*

-     * Can't alter reg_d's extents before we call pixman_op because

-     * it might be one of the source regions and pixman_op depends

-     * on the extents of those regions being unaltered. Besides, this

-     * way there's no checking against rectangles that will be nuked

-     * due to coalescing, so we have to examine fewer rectangles.

-     */

-    pixman_set_extents (reg_d);

-    GOOD (reg_d);

-    return TRUE;

-}

-

-/*======================================================================

- *	    Region Inversion

- *====================================================================*/

-

-/*-

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

- * pixman_region_inverse --

- *	Take a region and a box and return a region that is everything

- *	in the box but not in the region. The careful reader will note

- *	that this is the same as subtracting the region from the box...

- *

- * Results:

- *	TRUE.

- *

- * Side Effects:

- *	new_reg is overwritten.

- *

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

- */

-pixman_bool_t

-PIXMAN_EXPORT PREFIX (_inverse) (region_type_t *new_reg,  /* Destination region */

-                                 region_type_t *reg1,     /* Region to invert */

-                                 box_type_t *   inv_rect) /* Bounding box for inversion */

-{

-    region_type_t inv_reg; /* Quick and dirty region made from the

-			    * bounding box */

-    int overlap;           /* result ignored */

-

-    GOOD (reg1);

-    GOOD (new_reg);

-    

-    /* check for trivial rejects */

-    if (PIXREGION_NIL (reg1) || !EXTENTCHECK (inv_rect, &reg1->extents))

-    {

-        if (PIXREGION_NAR (reg1))

-	    return pixman_break (new_reg);

-	

-        new_reg->extents = *inv_rect;

-        FREE_DATA (new_reg);

-        new_reg->data = (region_data_type_t *)NULL;

-	

-        return TRUE;

-    }

-

-    /* Add those rectangles in region 1 that aren't in region 2,

-     * do yucky substraction for overlaps, and

-     * just throw away rectangles in region 2 that aren't in region 1

-     */

-    inv_reg.extents = *inv_rect;

-    inv_reg.data = (region_data_type_t *)NULL;

-    if (!pixman_op (new_reg, &inv_reg, reg1, pixman_region_subtract_o, TRUE, FALSE, &overlap))

-	return FALSE;

-

-    /*

-     * Can't alter new_reg's extents before we call pixman_op because

-     * it might be one of the source regions and pixman_op depends

-     * on the extents of those regions being unaltered. Besides, this

-     * way there's no checking against rectangles that will be nuked

-     * due to coalescing, so we have to examine fewer rectangles.

-     */

-    pixman_set_extents (new_reg);

-    GOOD (new_reg);

-    return TRUE;

-}

-

-/*

- *   rect_in(region, rect)

- *   This routine takes a pointer to a region and a pointer to a box

- *   and determines if the box is outside/inside/partly inside the region.

- *

- *   The idea is to travel through the list of rectangles trying to cover the

- *   passed box with them. Anytime a piece of the rectangle isn't covered

- *   by a band of rectangles, part_out is set TRUE. Any time a rectangle in

- *   the region covers part of the box, part_in is set TRUE. The process ends

- *   when either the box has been completely covered (we reached a band that

- *   doesn't overlap the box, part_in is TRUE and part_out is false), the

- *   box has been partially covered (part_in == part_out == TRUE -- because of

- *   the banding, the first time this is true we know the box is only

- *   partially in the region) or is outside the region (we reached a band

- *   that doesn't overlap the box at all and part_in is false)

- */

-

-pixman_region_overlap_t

-PIXMAN_EXPORT PREFIX (_contains_rectangle) (region_type_t *  region,

-                                            box_type_t *     prect)

-{

-    box_type_t *     pbox;

-    box_type_t *     pbox_end;

-    int part_in, part_out;

-    int numRects;

-    int x, y;

-

-    GOOD (region);

-

-    numRects = PIXREGION_NUMRECTS (region);

-

-    /* useful optimization */

-    if (!numRects || !EXTENTCHECK (&region->extents, prect))

-	return(PIXMAN_REGION_OUT);

-

-    if (numRects == 1)

-    {

-        /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */

-        if (SUBSUMES (&region->extents, prect))

-	    return(PIXMAN_REGION_IN);

-        else

-	    return(PIXMAN_REGION_PART);

-    }

-

-    part_out = FALSE;

-    part_in = FALSE;

-

-    /* (x,y) starts at upper left of rect, moving to the right and down */

-    x = prect->x1;

-    y = prect->y1;

-

-    /* can stop when both part_out and part_in are TRUE, or we reach prect->y2 */

-    for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;

-         pbox != pbox_end;

-         pbox++)

-    {

-

-        if (pbox->y2 <= y)

-	    continue;   /* getting up to speed or skipping remainder of band */

-

-        if (pbox->y1 > y)

-        {

-            part_out = TRUE;     /* missed part of rectangle above */

-            if (part_in || (pbox->y1 >= prect->y2))

-		break;

-            y = pbox->y1;       /* x guaranteed to be == prect->x1 */

-	}

-

-        if (pbox->x2 <= x)

-	    continue;           /* not far enough over yet */

-

-        if (pbox->x1 > x)

-        {

-            part_out = TRUE;     /* missed part of rectangle to left */

-            if (part_in)

-		break;

-	}

-

-        if (pbox->x1 < prect->x2)

-        {

-            part_in = TRUE;      /* definitely overlap */

-            if (part_out)

-		break;

-	}

-

-        if (pbox->x2 >= prect->x2)

-        {

-            y = pbox->y2;       /* finished with this band */

-            if (y >= prect->y2)

-		break;

-            x = prect->x1;      /* reset x out to left again */

-	}

-        else

-        {

-            /*

-	     * Because boxes in a band are maximal width, if the first box

-	     * to overlap the rectangle doesn't completely cover it in that

-	     * band, the rectangle must be partially out, since some of it

-	     * will be uncovered in that band. part_in will have been set true

-	     * by now...

-	     */

-            part_out = TRUE;

-            break;

-	}

-    }

-

-    if (part_in)

-    {

-        if (y < prect->y2)

-	    return PIXMAN_REGION_PART;

-        else

-	    return PIXMAN_REGION_IN;

-    }

-    else

-    {

-        return PIXMAN_REGION_OUT;

-    }

-}

-

-/* PREFIX(_translate) (region, x, y)

- * translates in place

- */

-

-PIXMAN_EXPORT void

-PREFIX (_translate) (region_type_t *region, int x, int y)

-{

-    overflow_int_t x1, x2, y1, y2;

-    int nbox;

-    box_type_t * pbox;

-

-    GOOD (region);

-    region->extents.x1 = x1 = region->extents.x1 + x;

-    region->extents.y1 = y1 = region->extents.y1 + y;

-    region->extents.x2 = x2 = region->extents.x2 + x;

-    region->extents.y2 = y2 = region->extents.y2 + y;

-    

-    if (((x1 - PIXMAN_REGION_MIN) | (y1 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x2) | (PIXMAN_REGION_MAX - y2)) >= 0)

-    {

-        if (region->data && (nbox = region->data->numRects))

-        {

-            for (pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)

-            {

-                pbox->x1 += x;

-                pbox->y1 += y;

-                pbox->x2 += x;

-                pbox->y2 += y;

-	    }

-	}

-        return;

-    }

-

-    if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)

-    {

-        region->extents.x2 = region->extents.x1;

-        region->extents.y2 = region->extents.y1;

-        FREE_DATA (region);

-        region->data = pixman_region_empty_data;

-        return;

-    }

-

-    if (x1 < PIXMAN_REGION_MIN)

-	region->extents.x1 = PIXMAN_REGION_MIN;

-    else if (x2 > PIXMAN_REGION_MAX)

-	region->extents.x2 = PIXMAN_REGION_MAX;

-

-    if (y1 < PIXMAN_REGION_MIN)

-	region->extents.y1 = PIXMAN_REGION_MIN;

-    else if (y2 > PIXMAN_REGION_MAX)

-	region->extents.y2 = PIXMAN_REGION_MAX;

-

-    if (region->data && (nbox = region->data->numRects))

-    {

-        box_type_t * pbox_out;

-

-        for (pbox_out = pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)

-        {

-            pbox_out->x1 = x1 = pbox->x1 + x;

-            pbox_out->y1 = y1 = pbox->y1 + y;

-            pbox_out->x2 = x2 = pbox->x2 + x;

-            pbox_out->y2 = y2 = pbox->y2 + y;

-

-            if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) |

-                 (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)

-            {

-                region->data->numRects--;

-                continue;

-	    }

-

-            if (x1 < PIXMAN_REGION_MIN)

-		pbox_out->x1 = PIXMAN_REGION_MIN;

-            else if (x2 > PIXMAN_REGION_MAX)

-		pbox_out->x2 = PIXMAN_REGION_MAX;

-

-            if (y1 < PIXMAN_REGION_MIN)

-		pbox_out->y1 = PIXMAN_REGION_MIN;

-            else if (y2 > PIXMAN_REGION_MAX)

-		pbox_out->y2 = PIXMAN_REGION_MAX;

-

-            pbox_out++;

-	}

-

-        if (pbox_out != pbox)

-        {

-            if (region->data->numRects == 1)

-            {

-                region->extents = *PIXREGION_BOXPTR (region);

-                FREE_DATA (region);

-                region->data = (region_data_type_t *)NULL;

-	    }

-            else

-	    {

-		pixman_set_extents (region);

-	    }

-	}

-    }

-

-    GOOD (region);

-}

-

-PIXMAN_EXPORT void

-PREFIX (_reset) (region_type_t *region, box_type_t *box)

-{

-    GOOD (region);

-

-    critical_if_fail (GOOD_RECT (box));

-

-    region->extents = *box;

-

-    FREE_DATA (region);

-

-    region->data = NULL;

-}

-

-/* box is "return" value */

-PIXMAN_EXPORT int

-PREFIX (_contains_point) (region_type_t * region,

-                          int x, int y,

-                          box_type_t * box)

-{

-    box_type_t *pbox, *pbox_end;

-    int numRects;

-

-    GOOD (region);

-    numRects = PIXREGION_NUMRECTS (region);

-

-    if (!numRects || !INBOX (&region->extents, x, y))

-	return(FALSE);

-

-    if (numRects == 1)

-    {

-        if (box)

-	    *box = region->extents;

-

-        return(TRUE);

-    }

-

-    for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;

-	 pbox != pbox_end;

-	 pbox++)

-    {

-        if (y >= pbox->y2)

-	    continue;           /* not there yet */

-

-        if ((y < pbox->y1) || (x < pbox->x1))

-	    break;              /* missed it */

-

-        if (x >= pbox->x2)

-	    continue;           /* not there yet */

-

-        if (box)

-	    *box = *pbox;

-

-        return(TRUE);

-    }

-

-    return(FALSE);

-}

-

-PIXMAN_EXPORT int

-PREFIX (_not_empty) (region_type_t * region)

-{

-    GOOD (region);

-

-    return(!PIXREGION_NIL (region));

-}

-

-PIXMAN_EXPORT box_type_t *

-PREFIX (_extents) (region_type_t * region)

-{

-    GOOD (region);

-

-    return(&region->extents);

-}

-

-/*

- * Clip a list of scanlines to a region.  The caller has allocated the

- * space.  FSorted is non-zero if the scanline origins are in ascending order.

- *

- * returns the number of new, clipped scanlines.

- */

-

-PIXMAN_EXPORT pixman_bool_t

-PREFIX (_selfcheck) (region_type_t *reg)

-{

-    int i, numRects;

-

-    if ((reg->extents.x1 > reg->extents.x2) ||

-        (reg->extents.y1 > reg->extents.y2))

-    {

-	return FALSE;

-    }

-

-    numRects = PIXREGION_NUMRECTS (reg);

-    if (!numRects)

-    {

-	return ((reg->extents.x1 == reg->extents.x2) &&

-	        (reg->extents.y1 == reg->extents.y2) &&

-	        (reg->data->size || (reg->data == pixman_region_empty_data)));

-    }

-    else if (numRects == 1)

-    {

-	return (!reg->data);

-    }

-    else

-    {

-        box_type_t * pbox_p, * pbox_n;

-        box_type_t box;

-

-        pbox_p = PIXREGION_RECTS (reg);

-        box = *pbox_p;

-        box.y2 = pbox_p[numRects - 1].y2;

-        pbox_n = pbox_p + 1;

-

-        for (i = numRects; --i > 0; pbox_p++, pbox_n++)

-        {

-            if ((pbox_n->x1 >= pbox_n->x2) ||

-                (pbox_n->y1 >= pbox_n->y2))

-	    {

-		return FALSE;

-	    }

-

-            if (pbox_n->x1 < box.x1)

-		box.x1 = pbox_n->x1;

-	    

-            if (pbox_n->x2 > box.x2)

-		box.x2 = pbox_n->x2;

-	    

-            if ((pbox_n->y1 < pbox_p->y1) ||

-                ((pbox_n->y1 == pbox_p->y1) &&

-                 ((pbox_n->x1 < pbox_p->x2) || (pbox_n->y2 != pbox_p->y2))))

-	    {

-		return FALSE;

-	    }

-	}

-

-        return ((box.x1 == reg->extents.x1) &&

-                (box.x2 == reg->extents.x2) &&

-                (box.y1 == reg->extents.y1) &&

-                (box.y2 == reg->extents.y2));

-    }

-}

-

-PIXMAN_EXPORT pixman_bool_t

-PREFIX (_init_rects) (region_type_t *region,

-                      const box_type_t *boxes, int count)

-{

-    box_type_t *rects;

-    int displacement;

-    int i;

-

-    /* if it's 1, then we just want to set the extents, so call

-     * the existing method. */

-    if (count == 1)

-    {

-        PREFIX (_init_rect) (region,

-                             boxes[0].x1,

-                             boxes[0].y1,

-                             boxes[0].x2 - boxes[0].x1,

-                             boxes[0].y2 - boxes[0].y1);

-        return TRUE;

-    }

-

-    PREFIX (_init) (region);

-

-    /* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is

-     * a special case, and causing pixman_rect_alloc would cause

-     * us to leak memory (because the 0-rect case should be the

-     * static pixman_region_empty_data data).

-     */

-    if (count == 0)

-	return TRUE;

-

-    if (!pixman_rect_alloc (region, count))

-	return FALSE;

-

-    rects = PIXREGION_RECTS (region);

-

-    /* Copy in the rects */

-    memcpy (rects, boxes, sizeof(box_type_t) * count);

-    region->data->numRects = count;

-

-    /* Eliminate empty and malformed rectangles */

-    displacement = 0;

-

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

-    {

-        box_type_t *box = &rects[i];

-

-        if (box->x1 >= box->x2 || box->y1 >= box->y2)

-	    displacement++;

-        else if (displacement)

-	    rects[i - displacement] = rects[i];

-    }

-

-    region->data->numRects -= displacement;

-

-    /* If eliminating empty rectangles caused there

-     * to be only 0 or 1 rectangles, deal with that.

-     */

-    if (region->data->numRects == 0)

-    {

-        FREE_DATA (region);

-        PREFIX (_init) (region);

-

-        return TRUE;

-    }

-

-    if (region->data->numRects == 1)

-    {

-        region->extents = rects[0];

-

-        FREE_DATA (region);

-        region->data = NULL;

-

-        GOOD (region);

-

-        return TRUE;

-    }

-

-    /* Validate */

-    region->extents.x1 = region->extents.x2 = 0;

-

-    return validate (region, &i);

-}

-

-#define READ(_ptr) (*(_ptr))

-

-static inline box_type_t *

-bitmap_addrect (region_type_t *reg,

-                box_type_t *r,

-                box_type_t **first_rect,

-                int rx1, int ry1,

-                int rx2, int ry2)

-{

-    if ((rx1 < rx2) && (ry1 < ry2) &&

-	(!(reg->data->numRects &&

-	   ((r-1)->y1 == ry1) && ((r-1)->y2 == ry2) &&

-	   ((r-1)->x1 <= rx1) && ((r-1)->x2 >= rx2))))

-    {

-	if (!reg->data ||

-	    reg->data->numRects == reg->data->size)

-	{

-	    if (!pixman_rect_alloc (reg, 1))

-		return NULL;

-	    *first_rect = PIXREGION_BOXPTR(reg);

-	    r = *first_rect + reg->data->numRects;

-	}

-	r->x1 = rx1;

-	r->y1 = ry1;

-	r->x2 = rx2;

-	r->y2 = ry2;

-	reg->data->numRects++;

-	if (r->x1 < reg->extents.x1)

-	    reg->extents.x1 = r->x1;

-	if (r->x2 > reg->extents.x2)

-	    reg->extents.x2 = r->x2;

-	r++;

-    }

-    return r;

-}

-

-/* Convert bitmap clip mask into clipping region.

- * First, goes through each line and makes boxes by noting the transitions

- * from 0 to 1 and 1 to 0.

- * Then it coalesces the current line with the previous if they have boxes

- * at the same X coordinates.

- * Stride is in number of uint32_t per line.

- */

-PIXMAN_EXPORT void

-PREFIX (_init_from_image) (region_type_t *region,

-                           pixman_image_t *image)

-{

-    uint32_t mask0 = 0xffffffff & ~SCREEN_SHIFT_RIGHT(0xffffffff, 1);

-    box_type_t *first_rect, *rects, *prect_line_start;

-    box_type_t *old_rect, *new_rect;

-    uint32_t *pw, w, *pw_line, *pw_line_end;

-    int	irect_prev_start, irect_line_start;

-    int	h, base, rx1 = 0, crects;

-    int	ib;

-    pixman_bool_t in_box, same;

-    int width, height, stride;

-

-    PREFIX(_init) (region);

-

-    return_if_fail (image->type == BITS);

-    return_if_fail (image->bits.format == PIXMAN_a1);

-

-    pw_line = pixman_image_get_data (image);

-    width = pixman_image_get_width (image);

-    height = pixman_image_get_height (image);

-    stride = pixman_image_get_stride (image) / 4;

-

-    first_rect = PIXREGION_BOXPTR(region);

-    rects = first_rect;

-

-    region->extents.x1 = width - 1;

-    region->extents.x2 = 0;

-    irect_prev_start = -1;

-    for (h = 0; h < height; h++)

-    {

-        pw = pw_line;

-        pw_line += stride;

-        irect_line_start = rects - first_rect;

-

-        /* If the Screen left most bit of the word is set, we're starting in

-         * a box */

-        if (READ(pw) & mask0)

-        {

-            in_box = TRUE;

-            rx1 = 0;

-        }

-        else

-        {

-            in_box = FALSE;

-        }

-

-        /* Process all words which are fully in the pixmap */

-        pw_line_end = pw + (width >> 5);

-        for (base = 0; pw < pw_line_end; base += 32)

-        {

-            w = READ(pw++);

-            if (in_box)

-            {

-                if (!~w)

-                    continue;

-            }

-            else

-            {

-                if (!w)

-                    continue;

-            }

-            for (ib = 0; ib < 32; ib++)

-            {

-                /* If the Screen left most bit of the word is set, we're

-                 * starting a box */

-                if (w & mask0)

-                {

-                    if (!in_box)

-                    {

-                        rx1 = base + ib;

-                        /* start new box */

-                        in_box = TRUE;

-                    }

-                }

-                else

-                {

-                    if (in_box)

-                    {

-                        /* end box */

-                        rects = bitmap_addrect (region, rects, &first_rect,

-                                                rx1, h, base + ib, h + 1);

-                        if (rects == NULL)

-                            goto error;

-                        in_box = FALSE;

-                    }

-                }

-                /* Shift the word VISUALLY left one. */

-                w = SCREEN_SHIFT_LEFT(w, 1);

-            }

-        }

-

-        if (width & 31)

-        {

-            /* Process final partial word on line */

-             w = READ(pw++);

-            for (ib = 0; ib < (width & 31); ib++)

-            {

-                /* If the Screen left most bit of the word is set, we're

-                 * starting a box */

-                if (w & mask0)

-                {

-                    if (!in_box)

-                    {

-                        rx1 = base + ib;

-                        /* start new box */

-                        in_box = TRUE;

-                    }

-                }

-                else

-                {

-                    if (in_box)

-                    {

-                        /* end box */

-                        rects = bitmap_addrect(region, rects, &first_rect,

-					       rx1, h, base + ib, h + 1);

-			if (rects == NULL)

-			    goto error;

-                        in_box = FALSE;

-                    }

-                }

-                /* Shift the word VISUALLY left one. */

-                w = SCREEN_SHIFT_LEFT(w, 1);

-            }

-        }

-        /* If scanline ended with last bit set, end the box */

-        if (in_box)

-        {

-            rects = bitmap_addrect(region, rects, &first_rect,

-				   rx1, h, base + (width & 31), h + 1);

-	    if (rects == NULL)

-		goto error;

-        }

-        /* if all rectangles on this line have the same x-coords as

-         * those on the previous line, then add 1 to all the previous  y2s and

-         * throw away all the rectangles from this line

-         */

-        same = FALSE;

-        if (irect_prev_start != -1)

-        {

-            crects = irect_line_start - irect_prev_start;

-            if (crects != 0 &&

-                crects == ((rects - first_rect) - irect_line_start))

-            {

-                old_rect = first_rect + irect_prev_start;

-                new_rect = prect_line_start = first_rect + irect_line_start;

-                same = TRUE;

-                while (old_rect < prect_line_start)

-                {

-                    if ((old_rect->x1 != new_rect->x1) ||

-                        (old_rect->x2 != new_rect->x2))

-                    {

-                          same = FALSE;

-                          break;

-                    }

-                    old_rect++;

-                    new_rect++;

-                }

-                if (same)

-                {

-                    old_rect = first_rect + irect_prev_start;

-                    while (old_rect < prect_line_start)

-                    {

-                        old_rect->y2 += 1;

-                        old_rect++;

-                    }

-                    rects -= crects;

-                    region->data->numRects -= crects;

-                }

-            }

-        }

-        if(!same)

-            irect_prev_start = irect_line_start;

-    }

-    if (!region->data->numRects)

-    {

-        region->extents.x1 = region->extents.x2 = 0;

-    }

-    else

-    {

-        region->extents.y1 = PIXREGION_BOXPTR(region)->y1;

-        region->extents.y2 = PIXREGION_END(region)->y2;

-        if (region->data->numRects == 1)

-        {

-            free (region->data);

-            region->data = NULL;

-        }

-    }

-

- error:

-    return;

-}

+/*
+ * Copyright 1987, 1988, 1989, 1998  The Open Group
+ * 
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation.
+ * 
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+ * OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
+ * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ * Except as contained in this notice, the name of The Open Group shall not be
+ * used in advertising or otherwise to promote the sale, use or other dealings
+ * in this Software without prior written authorization from The Open Group.
+ * 
+ * Copyright 1987, 1988, 1989 by
+ * Digital Equipment Corporation, Maynard, Massachusetts.
+ * 
+ *                    All Rights Reserved
+ * 
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation for any purpose and without fee is hereby granted,
+ * provided that the above copyright notice appear in all copies and that
+ * both that copyright notice and this permission notice appear in
+ * supporting documentation, and that the name of Digital not be
+ * used in advertising or publicity pertaining to distribution of the
+ * software without specific, written prior permission.
+ * 
+ * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
+ * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
+ * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
+ * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
+ * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
+ * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
+ * SOFTWARE.
+ *
+ * Copyright © 1998 Keith Packard
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Keith Packard makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
+ *
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <stdlib.h>
+#include <limits.h>
+#include <string.h>
+#include <stdio.h>
+#include "pixman-private.h"
+
+#define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
+/* not a region */
+#define PIXREGION_NAR(reg)      ((reg)->data == pixman_broken_data)
+#define PIXREGION_NUMRECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)
+#define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)
+#define PIXREGION_RECTS(reg) \
+    ((reg)->data ? (box_type_t *)((reg)->data + 1) \
+     : &(reg)->extents)
+#define PIXREGION_BOXPTR(reg) ((box_type_t *)((reg)->data + 1))
+#define PIXREGION_BOX(reg, i) (&PIXREGION_BOXPTR (reg)[i])
+#define PIXREGION_TOP(reg) PIXREGION_BOX (reg, (reg)->data->numRects)
+#define PIXREGION_END(reg) PIXREGION_BOX (reg, (reg)->data->numRects - 1)
+
+#define GOOD_RECT(rect) ((rect)->x1 < (rect)->x2 && (rect)->y1 < (rect)->y2)
+#define BAD_RECT(rect) ((rect)->x1 > (rect)->x2 || (rect)->y1 > (rect)->y2)
+
+#ifdef DEBUG
+
+#define GOOD(reg)							\
+    do									\
+    {									\
+	if (!PREFIX (_selfcheck (reg)))					\
+	    _pixman_log_error (FUNC, "Malformed region " # reg);	\
+    } while (0)
+
+#else
+
+#define GOOD(reg)
+
+#endif
+
+static const box_type_t PREFIX (_empty_box_) = { 0, 0, 0, 0 };
+static const region_data_type_t PREFIX (_empty_data_) = { 0, 0 };
+static const region_data_type_t PREFIX (_broken_data_) = { 0, 0 };
+
+static box_type_t *pixman_region_empty_box =
+    (box_type_t *)&PREFIX (_empty_box_);
+static region_data_type_t *pixman_region_empty_data =
+    (region_data_type_t *)&PREFIX (_empty_data_);
+static region_data_type_t *pixman_broken_data =
+    (region_data_type_t *)&PREFIX (_broken_data_);
+
+static pixman_bool_t
+pixman_break (region_type_t *region);
+
+/*
+ * The functions in this file implement the Region abstraction used extensively
+ * throughout the X11 sample server. A Region is simply a set of disjoint
+ * (non-overlapping) rectangles, plus an "extent" rectangle which is the
+ * smallest single rectangle that contains all the non-overlapping rectangles.
+ *
+ * A Region is implemented as a "y-x-banded" array of rectangles.  This array
+ * imposes two degrees of order.  First, all rectangles are sorted by top side
+ * y coordinate first (y1), and then by left side x coordinate (x1).
+ *
+ * Furthermore, the rectangles are grouped into "bands".  Each rectangle in a
+ * band has the same top y coordinate (y1), and each has the same bottom y
+ * coordinate (y2).  Thus all rectangles in a band differ only in their left
+ * and right side (x1 and x2).  Bands are implicit in the array of rectangles:
+ * there is no separate list of band start pointers.
+ *
+ * The y-x band representation does not minimize rectangles.  In particular,
+ * if a rectangle vertically crosses a band (the rectangle has scanlines in
+ * the y1 to y2 area spanned by the band), then the rectangle may be broken
+ * down into two or more smaller rectangles stacked one atop the other.
+ *
+ *  -----------				    -----------
+ *  |         |				    |         |		    band 0
+ *  |         |  --------		    -----------  --------
+ *  |         |  |      |  in y-x banded    |         |  |      |   band 1
+ *  |         |  |      |  form is	    |         |  |      |
+ *  -----------  |      |		    -----------  --------
+ *               |      |				 |      |   band 2
+ *               --------				 --------
+ *
+ * An added constraint on the rectangles is that they must cover as much
+ * horizontal area as possible: no two rectangles within a band are allowed
+ * to touch.
+ *
+ * Whenever possible, bands will be merged together to cover a greater vertical
+ * distance (and thus reduce the number of rectangles). Two bands can be merged
+ * only if the bottom of one touches the top of the other and they have
+ * rectangles in the same places (of the same width, of course).
+ *
+ * Adam de Boor wrote most of the original region code.  Joel McCormack
+ * substantially modified or rewrote most of the core arithmetic routines, and
+ * added pixman_region_validate in order to support several speed improvements
+ * to pixman_region_validate_tree.  Bob Scheifler changed the representation
+ * to be more compact when empty or a single rectangle, and did a bunch of
+ * gratuitous reformatting. Carl Worth did further gratuitous reformatting
+ * while re-merging the server and client region code into libpixregion.
+ * Soren Sandmann did even more gratuitous reformatting.
+ */
+
+/*  true iff two Boxes overlap */
+#define EXTENTCHECK(r1, r2)	   \
+    (!( ((r1)->x2 <= (r2)->x1)  || \
+        ((r1)->x1 >= (r2)->x2)  || \
+        ((r1)->y2 <= (r2)->y1)  || \
+        ((r1)->y1 >= (r2)->y2) ) )
+
+/* true iff (x,y) is in Box */
+#define INBOX(r, x, y)	\
+    ( ((r)->x2 >  x) && \
+      ((r)->x1 <= x) && \
+      ((r)->y2 >  y) && \
+      ((r)->y1 <= y) )
+
+/* true iff Box r1 contains Box r2 */
+#define SUBSUMES(r1, r2)	\
+    ( ((r1)->x1 <= (r2)->x1) && \
+      ((r1)->x2 >= (r2)->x2) && \
+      ((r1)->y1 <= (r2)->y1) && \
+      ((r1)->y2 >= (r2)->y2) )
+
+static size_t
+PIXREGION_SZOF (size_t n)
+{
+    size_t size = n * sizeof(box_type_t);
+    
+    if (n > UINT32_MAX / sizeof(box_type_t))
+	return 0;
+
+    if (sizeof(region_data_type_t) > UINT32_MAX - size)
+	return 0;
+
+    return size + sizeof(region_data_type_t);
+}
+
+static void *
+alloc_data (size_t n)
+{
+    size_t sz = PIXREGION_SZOF (n);
+
+    if (!sz)
+	return NULL;
+
+    return malloc (sz);
+}
+
+#define FREE_DATA(reg) if ((reg)->data && (reg)->data->size) free ((reg)->data)
+
+#define RECTALLOC_BAIL(region, n, bail)					\
+    do									\
+    {									\
+	if (!(region)->data ||						\
+	    (((region)->data->numRects + (n)) > (region)->data->size))	\
+	{								\
+	    if (!pixman_rect_alloc (region, n))				\
+		goto bail;						\
+	}								\
+    } while (0)
+
+#define RECTALLOC(region, n)						\
+    do									\
+    {									\
+	if (!(region)->data ||						\
+	    (((region)->data->numRects + (n)) > (region)->data->size))	\
+	{								\
+	    if (!pixman_rect_alloc (region, n)) {			\
+		return FALSE;						\
+	    }								\
+	}								\
+    } while (0)
+
+#define ADDRECT(next_rect, nx1, ny1, nx2, ny2)      \
+    do						    \
+    {						    \
+	next_rect->x1 = nx1;                        \
+	next_rect->y1 = ny1;                        \
+	next_rect->x2 = nx2;                        \
+	next_rect->y2 = ny2;                        \
+	next_rect++;                                \
+    }						    \
+    while (0)
+
+#define NEWRECT(region, next_rect, nx1, ny1, nx2, ny2)			\
+    do									\
+    {									\
+	if (!(region)->data ||						\
+	    ((region)->data->numRects == (region)->data->size))		\
+	{								\
+	    if (!pixman_rect_alloc (region, 1))				\
+		return FALSE;						\
+	    next_rect = PIXREGION_TOP (region);				\
+	}								\
+	ADDRECT (next_rect, nx1, ny1, nx2, ny2);			\
+	region->data->numRects++;					\
+	critical_if_fail (region->data->numRects <= region->data->size);		\
+    } while (0)
+
+#define DOWNSIZE(reg, numRects)						\
+    do									\
+    {									\
+	if (((numRects) < ((reg)->data->size >> 1)) &&			\
+	    ((reg)->data->size > 50))					\
+	{								\
+	    region_data_type_t * new_data;				\
+	    size_t data_size = PIXREGION_SZOF (numRects);		\
+									\
+	    if (!data_size)						\
+	    {								\
+		new_data = NULL;					\
+	    }								\
+	    else							\
+	    {								\
+		new_data = (region_data_type_t *)			\
+		    realloc ((reg)->data, data_size);			\
+	    }								\
+									\
+	    if (new_data)						\
+	    {								\
+		new_data->size = (numRects);				\
+		(reg)->data = new_data;					\
+	    }								\
+	}								\
+    } while (0)
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_equal) (region_type_t *reg1, region_type_t *reg2)
+{
+    int i;
+    box_type_t *rects1;
+    box_type_t *rects2;
+
+    if (reg1->extents.x1 != reg2->extents.x1)
+	return FALSE;
+    
+    if (reg1->extents.x2 != reg2->extents.x2)
+	return FALSE;
+    
+    if (reg1->extents.y1 != reg2->extents.y1)
+	return FALSE;
+    
+    if (reg1->extents.y2 != reg2->extents.y2)
+	return FALSE;
+    
+    if (PIXREGION_NUMRECTS (reg1) != PIXREGION_NUMRECTS (reg2))
+	return FALSE;
+
+    rects1 = PIXREGION_RECTS (reg1);
+    rects2 = PIXREGION_RECTS (reg2);
+    
+    for (i = 0; i != PIXREGION_NUMRECTS (reg1); i++)
+    {
+	if (rects1[i].x1 != rects2[i].x1)
+	    return FALSE;
+	
+	if (rects1[i].x2 != rects2[i].x2)
+	    return FALSE;
+	
+	if (rects1[i].y1 != rects2[i].y1)
+	    return FALSE;
+	
+	if (rects1[i].y2 != rects2[i].y2)
+	    return FALSE;
+    }
+
+    return TRUE;
+}
+
+int
+PREFIX (_print) (region_type_t *rgn)
+{
+    int num, size;
+    int i;
+    box_type_t * rects;
+
+    num = PIXREGION_NUMRECTS (rgn);
+    size = PIXREGION_SIZE (rgn);
+    rects = PIXREGION_RECTS (rgn);
+
+    fprintf (stderr, "num: %d size: %d\n", num, size);
+    fprintf (stderr, "extents: %d %d %d %d\n",
+             rgn->extents.x1,
+	     rgn->extents.y1,
+	     rgn->extents.x2,
+	     rgn->extents.y2);
+    
+    for (i = 0; i < num; i++)
+    {
+	fprintf (stderr, "%d %d %d %d \n",
+	         rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
+    }
+    
+    fprintf (stderr, "\n");
+
+    return(num);
+}
+
+
+PIXMAN_EXPORT void
+PREFIX (_init) (region_type_t *region)
+{
+    region->extents = *pixman_region_empty_box;
+    region->data = pixman_region_empty_data;
+}
+
+PIXMAN_EXPORT void
+PREFIX (_init_rect) (region_type_t *	region,
+                     int		x,
+		     int		y,
+		     unsigned int	width,
+		     unsigned int	height)
+{
+    region->extents.x1 = x;
+    region->extents.y1 = y;
+    region->extents.x2 = x + width;
+    region->extents.y2 = y + height;
+
+    if (!GOOD_RECT (&region->extents))
+    {
+        if (BAD_RECT (&region->extents))
+            _pixman_log_error (FUNC, "Invalid rectangle passed");
+        PREFIX (_init) (region);
+        return;
+    }
+
+    region->data = NULL;
+}
+
+PIXMAN_EXPORT void
+PREFIX (_init_with_extents) (region_type_t *region, box_type_t *extents)
+{
+    if (!GOOD_RECT (extents))
+    {
+        if (BAD_RECT (extents))
+            _pixman_log_error (FUNC, "Invalid rectangle passed");
+        PREFIX (_init) (region);
+        return;
+    }
+    region->extents = *extents;
+
+    region->data = NULL;
+}
+
+PIXMAN_EXPORT void
+PREFIX (_fini) (region_type_t *region)
+{
+    GOOD (region);
+    FREE_DATA (region);
+}
+
+PIXMAN_EXPORT int
+PREFIX (_n_rects) (region_type_t *region)
+{
+    return PIXREGION_NUMRECTS (region);
+}
+
+PIXMAN_EXPORT box_type_t *
+PREFIX (_rectangles) (region_type_t *region,
+                      int               *n_rects)
+{
+    if (n_rects)
+	*n_rects = PIXREGION_NUMRECTS (region);
+
+    return PIXREGION_RECTS (region);
+}
+
+static pixman_bool_t
+pixman_break (region_type_t *region)
+{
+    FREE_DATA (region);
+
+    region->extents = *pixman_region_empty_box;
+    region->data = pixman_broken_data;
+
+    return FALSE;
+}
+
+static pixman_bool_t
+pixman_rect_alloc (region_type_t * region,
+                   int             n)
+{
+    region_data_type_t *data;
+
+    if (!region->data)
+    {
+	n++;
+	region->data = alloc_data (n);
+
+	if (!region->data)
+	    return pixman_break (region);
+
+	region->data->numRects = 1;
+	*PIXREGION_BOXPTR (region) = region->extents;
+    }
+    else if (!region->data->size)
+    {
+	region->data = alloc_data (n);
+
+	if (!region->data)
+	    return pixman_break (region);
+
+	region->data->numRects = 0;
+    }
+    else
+    {
+	size_t data_size;
+
+	if (n == 1)
+	{
+	    n = region->data->numRects;
+	    if (n > 500) /* XXX pick numbers out of a hat */
+		n = 250;
+	}
+
+	n += region->data->numRects;
+	data_size = PIXREGION_SZOF (n);
+
+	if (!data_size)
+	{
+	    data = NULL;
+	}
+	else
+	{
+	    data = (region_data_type_t *)
+		realloc (region->data, PIXREGION_SZOF (n));
+	}
+	
+	if (!data)
+	    return pixman_break (region);
+	
+	region->data = data;
+    }
+    
+    region->data->size = n;
+
+    return TRUE;
+}
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_copy) (region_type_t *dst, region_type_t *src)
+{
+    GOOD (dst);
+    GOOD (src);
+
+    if (dst == src)
+	return TRUE;
+    
+    dst->extents = src->extents;
+
+    if (!src->data || !src->data->size)
+    {
+	FREE_DATA (dst);
+	dst->data = src->data;
+	return TRUE;
+    }
+    
+    if (!dst->data || (dst->data->size < src->data->numRects))
+    {
+	FREE_DATA (dst);
+
+	dst->data = alloc_data (src->data->numRects);
+
+	if (!dst->data)
+	    return pixman_break (dst);
+
+	dst->data->size = src->data->numRects;
+    }
+
+    dst->data->numRects = src->data->numRects;
+
+    memmove ((char *)PIXREGION_BOXPTR (dst), (char *)PIXREGION_BOXPTR (src),
+             dst->data->numRects * sizeof(box_type_t));
+
+    return TRUE;
+}
+
+/*======================================================================
+ *	    Generic Region Operator
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_coalesce --
+ *	Attempt to merge the boxes in the current band with those in the
+ *	previous one.  We are guaranteed that the current band extends to
+ *      the end of the rects array.  Used only by pixman_op.
+ *
+ * Results:
+ *	The new index for the previous band.
+ *
+ * Side Effects:
+ *	If coalescing takes place:
+ *	    - rectangles in the previous band will have their y2 fields
+ *	      altered.
+ *	    - region->data->numRects will be decreased.
+ *
+ *-----------------------------------------------------------------------
+ */
+static inline int
+pixman_coalesce (region_type_t * region,      /* Region to coalesce		 */
+		 int             prev_start,  /* Index of start of previous band */
+		 int             cur_start)   /* Index of start of current band  */
+{
+    box_type_t *prev_box;       /* Current box in previous band	     */
+    box_type_t *cur_box;        /* Current box in current band       */
+    int numRects;               /* Number rectangles in both bands   */
+    int y2;                     /* Bottom of current band	     */
+
+    /*
+     * Figure out how many rectangles are in the band.
+     */
+    numRects = cur_start - prev_start;
+    critical_if_fail (numRects == region->data->numRects - cur_start);
+
+    if (!numRects) return cur_start;
+
+    /*
+     * The bands may only be coalesced if the bottom of the previous
+     * matches the top scanline of the current.
+     */
+    prev_box = PIXREGION_BOX (region, prev_start);
+    cur_box = PIXREGION_BOX (region, cur_start);
+    if (prev_box->y2 != cur_box->y1) return cur_start;
+
+    /*
+     * Make sure the bands have boxes in the same places. This
+     * assumes that boxes have been added in such a way that they
+     * cover the most area possible. I.e. two boxes in a band must
+     * have some horizontal space between them.
+     */
+    y2 = cur_box->y2;
+
+    do
+    {
+	if ((prev_box->x1 != cur_box->x1) || (prev_box->x2 != cur_box->x2))
+	    return (cur_start);
+	
+	prev_box++;
+	cur_box++;
+	numRects--;
+    }
+    while (numRects);
+
+    /*
+     * The bands may be merged, so set the bottom y of each box
+     * in the previous band to the bottom y of the current band.
+     */
+    numRects = cur_start - prev_start;
+    region->data->numRects -= numRects;
+
+    do
+    {
+	prev_box--;
+	prev_box->y2 = y2;
+	numRects--;
+    }
+    while (numRects);
+
+    return prev_start;
+}
+
+/* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
+
+#define COALESCE(new_reg, prev_band, cur_band)                          \
+    do									\
+    {									\
+	if (cur_band - prev_band == new_reg->data->numRects - cur_band)	\
+	    prev_band = pixman_coalesce (new_reg, prev_band, cur_band);	\
+	else								\
+	    prev_band = cur_band;					\
+    } while (0)
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_append_non_o --
+ *	Handle a non-overlapping band for the union and subtract operations.
+ *      Just adds the (top/bottom-clipped) rectangles into the region.
+ *      Doesn't have to check for subsumption or anything.
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	region->data->numRects is incremented and the rectangles overwritten
+ *	with the rectangles we're passed.
+ *
+ *-----------------------------------------------------------------------
+ */
+static inline pixman_bool_t
+pixman_region_append_non_o (region_type_t * region,
+			    box_type_t *    r,
+			    box_type_t *    r_end,
+			    int             y1,
+			    int             y2)
+{
+    box_type_t *next_rect;
+    int new_rects;
+
+    new_rects = r_end - r;
+
+    critical_if_fail (y1 < y2);
+    critical_if_fail (new_rects != 0);
+
+    /* Make sure we have enough space for all rectangles to be added */
+    RECTALLOC (region, new_rects);
+    next_rect = PIXREGION_TOP (region);
+    region->data->numRects += new_rects;
+
+    do
+    {
+	critical_if_fail (r->x1 < r->x2);
+	ADDRECT (next_rect, r->x1, y1, r->x2, y2);
+	r++;
+    }
+    while (r != r_end);
+
+    return TRUE;
+}
+
+#define FIND_BAND(r, r_band_end, r_end, ry1)			     \
+    do								     \
+    {								     \
+	ry1 = r->y1;						     \
+	r_band_end = r + 1;					     \
+	while ((r_band_end != r_end) && (r_band_end->y1 == ry1)) {   \
+	    r_band_end++;					     \
+	}							     \
+    } while (0)
+
+#define APPEND_REGIONS(new_reg, r, r_end)				\
+    do									\
+    {									\
+	int new_rects;							\
+	if ((new_rects = r_end - r)) {					\
+	    RECTALLOC_BAIL (new_reg, new_rects, bail);			\
+	    memmove ((char *)PIXREGION_TOP (new_reg), (char *)r,	\
+		     new_rects * sizeof(box_type_t));			\
+	    new_reg->data->numRects += new_rects;			\
+	}								\
+    } while (0)
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_op --
+ *	Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,
+ *	pixman_region_subtract, pixman_region_intersect....  Both regions MUST have at least one
+ *      rectangle, and cannot be the same object.
+ *
+ * Results:
+ *	TRUE if successful.
+ *
+ * Side Effects:
+ *	The new region is overwritten.
+ *	overlap set to TRUE if overlap_func ever returns TRUE.
+ *
+ * Notes:
+ *	The idea behind this function is to view the two regions as sets.
+ *	Together they cover a rectangle of area that this function divides
+ *	into horizontal bands where points are covered only by one region
+ *	or by both. For the first case, the non_overlap_func is called with
+ *	each the band and the band's upper and lower extents. For the
+ *	second, the overlap_func is called to process the entire band. It
+ *	is responsible for clipping the rectangles in the band, though
+ *	this function provides the boundaries.
+ *	At the end of each band, the new region is coalesced, if possible,
+ *	to reduce the number of rectangles in the region.
+ *
+ *-----------------------------------------------------------------------
+ */
+
+typedef pixman_bool_t (*overlap_proc_ptr) (region_type_t *region,
+					   box_type_t *   r1,
+					   box_type_t *   r1_end,
+					   box_type_t *   r2,
+					   box_type_t *   r2_end,
+					   int            y1,
+					   int            y2,
+					   int *          overlap);
+
+static pixman_bool_t
+pixman_op (region_type_t *  new_reg,               /* Place to store result	    */
+	   region_type_t *  reg1,                  /* First region in operation     */
+	   region_type_t *  reg2,                  /* 2d region in operation        */
+	   overlap_proc_ptr overlap_func,          /* Function to call for over-
+						    * lapping bands		    */
+	   int              append_non1,           /* Append non-overlapping bands  
+						    * in region 1 ?
+						    */
+	   int              append_non2,           /* Append non-overlapping bands
+						    * in region 2 ?
+						    */
+	   int *            overlap)
+{
+    box_type_t *r1;                 /* Pointer into first region     */
+    box_type_t *r2;                 /* Pointer into 2d region	     */
+    box_type_t *r1_end;             /* End of 1st region	     */
+    box_type_t *r2_end;             /* End of 2d region		     */
+    int ybot;                       /* Bottom of intersection	     */
+    int ytop;                       /* Top of intersection	     */
+    region_data_type_t *old_data;   /* Old data for new_reg	     */
+    int prev_band;                  /* Index of start of
+				     * previous band in new_reg       */
+    int cur_band;                   /* Index of start of current
+				     * band in new_reg		     */
+    box_type_t * r1_band_end;       /* End of current band in r1     */
+    box_type_t * r2_band_end;       /* End of current band in r2     */
+    int top;                        /* Top of non-overlapping band   */
+    int bot;                        /* Bottom of non-overlapping band*/
+    int r1y1;                       /* Temps for r1->y1 and r2->y1   */
+    int r2y1;
+    int new_size;
+    int numRects;
+
+    /*
+     * Break any region computed from a broken region
+     */
+    if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))
+	return pixman_break (new_reg);
+
+    /*
+     * Initialization:
+     *	set r1, r2, r1_end and r2_end appropriately, save the rectangles
+     * of the destination region until the end in case it's one of
+     * the two source regions, then mark the "new" region empty, allocating
+     * another array of rectangles for it to use.
+     */
+
+    r1 = PIXREGION_RECTS (reg1);
+    new_size = PIXREGION_NUMRECTS (reg1);
+    r1_end = r1 + new_size;
+
+    numRects = PIXREGION_NUMRECTS (reg2);
+    r2 = PIXREGION_RECTS (reg2);
+    r2_end = r2 + numRects;
+    
+    critical_if_fail (r1 != r1_end);
+    critical_if_fail (r2 != r2_end);
+
+    old_data = (region_data_type_t *)NULL;
+
+    if (((new_reg == reg1) && (new_size > 1)) ||
+        ((new_reg == reg2) && (numRects > 1)))
+    {
+        old_data = new_reg->data;
+        new_reg->data = pixman_region_empty_data;
+    }
+
+    /* guess at new size */
+    if (numRects > new_size)
+	new_size = numRects;
+
+    new_size <<= 1;
+
+    if (!new_reg->data)
+	new_reg->data = pixman_region_empty_data;
+    else if (new_reg->data->size)
+	new_reg->data->numRects = 0;
+
+    if (new_size > new_reg->data->size)
+    {
+        if (!pixman_rect_alloc (new_reg, new_size))
+        {
+            if (old_data)
+		free (old_data);
+            return FALSE;
+	}
+    }
+
+    /*
+     * Initialize ybot.
+     * In the upcoming loop, ybot and ytop serve different functions depending
+     * on whether the band being handled is an overlapping or non-overlapping
+     * band.
+     *  In the case of a non-overlapping band (only one of the regions
+     * has points in the band), ybot is the bottom of the most recent
+     * intersection and thus clips the top of the rectangles in that band.
+     * ytop is the top of the next intersection between the two regions and
+     * serves to clip the bottom of the rectangles in the current band.
+     *	For an overlapping band (where the two regions intersect), ytop clips
+     * the top of the rectangles of both regions and ybot clips the bottoms.
+     */
+
+    ybot = MIN (r1->y1, r2->y1);
+
+    /*
+     * prev_band serves to mark the start of the previous band so rectangles
+     * can be coalesced into larger rectangles. qv. pixman_coalesce, above.
+     * In the beginning, there is no previous band, so prev_band == cur_band
+     * (cur_band is set later on, of course, but the first band will always
+     * start at index 0). prev_band and cur_band must be indices because of
+     * the possible expansion, and resultant moving, of the new region's
+     * array of rectangles.
+     */
+    prev_band = 0;
+
+    do
+    {
+        /*
+	 * This algorithm proceeds one source-band (as opposed to a
+	 * destination band, which is determined by where the two regions
+	 * intersect) at a time. r1_band_end and r2_band_end serve to mark the
+	 * rectangle after the last one in the current band for their
+	 * respective regions.
+	 */
+        critical_if_fail (r1 != r1_end);
+        critical_if_fail (r2 != r2_end);
+
+        FIND_BAND (r1, r1_band_end, r1_end, r1y1);
+        FIND_BAND (r2, r2_band_end, r2_end, r2y1);
+
+        /*
+	 * First handle the band that doesn't intersect, if any.
+	 *
+	 * Note that attention is restricted to one band in the
+	 * non-intersecting region at once, so if a region has n
+	 * bands between the current position and the next place it overlaps
+	 * the other, this entire loop will be passed through n times.
+	 */
+        if (r1y1 < r2y1)
+        {
+            if (append_non1)
+            {
+                top = MAX (r1y1, ybot);
+                bot = MIN (r1->y2, r2y1);
+                if (top != bot)
+                {
+                    cur_band = new_reg->data->numRects;
+                    if (!pixman_region_append_non_o (new_reg, r1, r1_band_end, top, bot))
+			goto bail;
+                    COALESCE (new_reg, prev_band, cur_band);
+		}
+	    }
+            ytop = r2y1;
+	}
+        else if (r2y1 < r1y1)
+        {
+            if (append_non2)
+            {
+                top = MAX (r2y1, ybot);
+                bot = MIN (r2->y2, r1y1);
+		
+                if (top != bot)
+                {
+                    cur_band = new_reg->data->numRects;
+
+                    if (!pixman_region_append_non_o (new_reg, r2, r2_band_end, top, bot))
+			goto bail;
+
+                    COALESCE (new_reg, prev_band, cur_band);
+		}
+	    }
+            ytop = r1y1;
+	}
+        else
+        {
+            ytop = r1y1;
+	}
+
+        /*
+	 * Now see if we've hit an intersecting band. The two bands only
+	 * intersect if ybot > ytop
+	 */
+        ybot = MIN (r1->y2, r2->y2);
+        if (ybot > ytop)
+        {
+            cur_band = new_reg->data->numRects;
+
+            if (!(*overlap_func)(new_reg,
+                                 r1, r1_band_end,
+                                 r2, r2_band_end,
+                                 ytop, ybot,
+                                 overlap))
+	    {
+		goto bail;
+	    }
+	    
+            COALESCE (new_reg, prev_band, cur_band);
+	}
+
+        /*
+	 * If we've finished with a band (y2 == ybot) we skip forward
+	 * in the region to the next band.
+	 */
+        if (r1->y2 == ybot)
+	    r1 = r1_band_end;
+
+        if (r2->y2 == ybot)
+	    r2 = r2_band_end;
+
+    }
+    while (r1 != r1_end && r2 != r2_end);
+
+    /*
+     * Deal with whichever region (if any) still has rectangles left.
+     *
+     * We only need to worry about banding and coalescing for the very first
+     * band left.  After that, we can just group all remaining boxes,
+     * regardless of how many bands, into one final append to the list.
+     */
+
+    if ((r1 != r1_end) && append_non1)
+    {
+        /* Do first non_overlap1Func call, which may be able to coalesce */
+        FIND_BAND (r1, r1_band_end, r1_end, r1y1);
+	
+        cur_band = new_reg->data->numRects;
+	
+        if (!pixman_region_append_non_o (new_reg,
+                                         r1, r1_band_end,
+                                         MAX (r1y1, ybot), r1->y2))
+	{
+	    goto bail;
+	}
+	
+        COALESCE (new_reg, prev_band, cur_band);
+
+        /* Just append the rest of the boxes  */
+        APPEND_REGIONS (new_reg, r1_band_end, r1_end);
+    }
+    else if ((r2 != r2_end) && append_non2)
+    {
+        /* Do first non_overlap2Func call, which may be able to coalesce */
+        FIND_BAND (r2, r2_band_end, r2_end, r2y1);
+
+	cur_band = new_reg->data->numRects;
+
+        if (!pixman_region_append_non_o (new_reg,
+                                         r2, r2_band_end,
+                                         MAX (r2y1, ybot), r2->y2))
+	{
+	    goto bail;
+	}
+
+        COALESCE (new_reg, prev_band, cur_band);
+
+        /* Append rest of boxes */
+        APPEND_REGIONS (new_reg, r2_band_end, r2_end);
+    }
+
+    if (old_data)
+	free (old_data);
+
+    if (!(numRects = new_reg->data->numRects))
+    {
+        FREE_DATA (new_reg);
+        new_reg->data = pixman_region_empty_data;
+    }
+    else if (numRects == 1)
+    {
+        new_reg->extents = *PIXREGION_BOXPTR (new_reg);
+        FREE_DATA (new_reg);
+        new_reg->data = (region_data_type_t *)NULL;
+    }
+    else
+    {
+        DOWNSIZE (new_reg, numRects);
+    }
+
+    return TRUE;
+
+bail:
+    if (old_data)
+	free (old_data);
+
+    return pixman_break (new_reg);
+}
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_set_extents --
+ *	Reset the extents of a region to what they should be. Called by
+ *	pixman_region_subtract and pixman_region_intersect as they can't
+ *      figure it out along the way or do so easily, as pixman_region_union can.
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	The region's 'extents' structure is overwritten.
+ *
+ *-----------------------------------------------------------------------
+ */
+static void
+pixman_set_extents (region_type_t *region)
+{
+    box_type_t *box, *box_end;
+
+    if (!region->data)
+	return;
+
+    if (!region->data->size)
+    {
+        region->extents.x2 = region->extents.x1;
+        region->extents.y2 = region->extents.y1;
+        return;
+    }
+
+    box = PIXREGION_BOXPTR (region);
+    box_end = PIXREGION_END (region);
+
+    /*
+     * Since box is the first rectangle in the region, it must have the
+     * smallest y1 and since box_end is the last rectangle in the region,
+     * it must have the largest y2, because of banding. Initialize x1 and
+     * x2 from  box and box_end, resp., as good things to initialize them
+     * to...
+     */
+    region->extents.x1 = box->x1;
+    region->extents.y1 = box->y1;
+    region->extents.x2 = box_end->x2;
+    region->extents.y2 = box_end->y2;
+
+    critical_if_fail (region->extents.y1 < region->extents.y2);
+
+    while (box <= box_end)
+    {
+        if (box->x1 < region->extents.x1)
+	    region->extents.x1 = box->x1;
+        if (box->x2 > region->extents.x2)
+	    region->extents.x2 = box->x2;
+        box++;
+    }
+
+    critical_if_fail (region->extents.x1 < region->extents.x2);
+}
+
+/*======================================================================
+ *	    Region Intersection
+ *====================================================================*/
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_intersect_o --
+ *	Handle an overlapping band for pixman_region_intersect.
+ *
+ * Results:
+ *	TRUE if successful.
+ *
+ * Side Effects:
+ *	Rectangles may be added to the region.
+ *
+ *-----------------------------------------------------------------------
+ */
+/*ARGSUSED*/
+static pixman_bool_t
+pixman_region_intersect_o (region_type_t *region,
+                           box_type_t *   r1,
+                           box_type_t *   r1_end,
+                           box_type_t *   r2,
+                           box_type_t *   r2_end,
+                           int            y1,
+                           int            y2,
+                           int *          overlap)
+{
+    int x1;
+    int x2;
+    box_type_t *        next_rect;
+
+    next_rect = PIXREGION_TOP (region);
+
+    critical_if_fail (y1 < y2);
+    critical_if_fail (r1 != r1_end && r2 != r2_end);
+
+    do
+    {
+        x1 = MAX (r1->x1, r2->x1);
+        x2 = MIN (r1->x2, r2->x2);
+
+        /*
+	 * If there's any overlap between the two rectangles, add that
+	 * overlap to the new region.
+	 */
+        if (x1 < x2)
+	    NEWRECT (region, next_rect, x1, y1, x2, y2);
+
+        /*
+	 * Advance the pointer(s) with the leftmost right side, since the next
+	 * rectangle on that list may still overlap the other region's
+	 * current rectangle.
+	 */
+        if (r1->x2 == x2)
+        {
+            r1++;
+	}
+        if (r2->x2 == x2)
+        {
+            r2++;
+	}
+    }
+    while ((r1 != r1_end) && (r2 != r2_end));
+
+    return TRUE;
+}
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_intersect) (region_type_t *     new_reg,
+                     region_type_t *        reg1,
+                     region_type_t *        reg2)
+{
+    GOOD (reg1);
+    GOOD (reg2);
+    GOOD (new_reg);
+
+    /* check for trivial reject */
+    if (PIXREGION_NIL (reg1) || PIXREGION_NIL (reg2) ||
+        !EXTENTCHECK (&reg1->extents, &reg2->extents))
+    {
+        /* Covers about 20% of all cases */
+        FREE_DATA (new_reg);
+        new_reg->extents.x2 = new_reg->extents.x1;
+        new_reg->extents.y2 = new_reg->extents.y1;
+        if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))
+        {
+            new_reg->data = pixman_broken_data;
+            return FALSE;
+	}
+        else
+	{
+	    new_reg->data = pixman_region_empty_data;
+	}
+    }
+    else if (!reg1->data && !reg2->data)
+    {
+        /* Covers about 80% of cases that aren't trivially rejected */
+        new_reg->extents.x1 = MAX (reg1->extents.x1, reg2->extents.x1);
+        new_reg->extents.y1 = MAX (reg1->extents.y1, reg2->extents.y1);
+        new_reg->extents.x2 = MIN (reg1->extents.x2, reg2->extents.x2);
+        new_reg->extents.y2 = MIN (reg1->extents.y2, reg2->extents.y2);
+
+        FREE_DATA (new_reg);
+
+	new_reg->data = (region_data_type_t *)NULL;
+    }
+    else if (!reg2->data && SUBSUMES (&reg2->extents, &reg1->extents))
+    {
+        return PREFIX (_copy) (new_reg, reg1);
+    }
+    else if (!reg1->data && SUBSUMES (&reg1->extents, &reg2->extents))
+    {
+        return PREFIX (_copy) (new_reg, reg2);
+    }
+    else if (reg1 == reg2)
+    {
+        return PREFIX (_copy) (new_reg, reg1);
+    }
+    else
+    {
+        /* General purpose intersection */
+        int overlap; /* result ignored */
+
+        if (!pixman_op (new_reg, reg1, reg2, pixman_region_intersect_o, FALSE, FALSE,
+                        &overlap))
+	{
+	    return FALSE;
+	}
+	
+        pixman_set_extents (new_reg);
+    }
+
+    GOOD (new_reg);
+    return(TRUE);
+}
+
+#define MERGERECT(r)							\
+    do									\
+    {									\
+        if (r->x1 <= x2)						\
+	{								\
+            /* Merge with current rectangle */				\
+            if (r->x1 < x2)						\
+		*overlap = TRUE;					\
+									\
+            if (x2 < r->x2)						\
+		x2 = r->x2;						\
+	}								\
+	else								\
+	{								\
+            /* Add current rectangle, start new one */			\
+            NEWRECT (region, next_rect, x1, y1, x2, y2);		\
+            x1 = r->x1;							\
+            x2 = r->x2;							\
+	}								\
+        r++;								\
+    } while (0)
+
+/*======================================================================
+ *	    Region Union
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_union_o --
+ *	Handle an overlapping band for the union operation. Picks the
+ *	left-most rectangle each time and merges it into the region.
+ *
+ * Results:
+ *	TRUE if successful.
+ *
+ * Side Effects:
+ *	region is overwritten.
+ *	overlap is set to TRUE if any boxes overlap.
+ *
+ *-----------------------------------------------------------------------
+ */
+static pixman_bool_t
+pixman_region_union_o (region_type_t *region,
+		       box_type_t *   r1,
+		       box_type_t *   r1_end,
+		       box_type_t *   r2,
+		       box_type_t *   r2_end,
+		       int            y1,
+		       int            y2,
+		       int *          overlap)
+{
+    box_type_t *next_rect;
+    int x1;            /* left and right side of current union */
+    int x2;
+
+    critical_if_fail (y1 < y2);
+    critical_if_fail (r1 != r1_end && r2 != r2_end);
+
+    next_rect = PIXREGION_TOP (region);
+
+    /* Start off current rectangle */
+    if (r1->x1 < r2->x1)
+    {
+        x1 = r1->x1;
+        x2 = r1->x2;
+        r1++;
+    }
+    else
+    {
+        x1 = r2->x1;
+        x2 = r2->x2;
+        r2++;
+    }
+    while (r1 != r1_end && r2 != r2_end)
+    {
+        if (r1->x1 < r2->x1)
+	    MERGERECT (r1);
+	else
+	    MERGERECT (r2);
+    }
+
+    /* Finish off whoever (if any) is left */
+    if (r1 != r1_end)
+    {
+        do
+        {
+            MERGERECT (r1);
+	}
+        while (r1 != r1_end);
+    }
+    else if (r2 != r2_end)
+    {
+        do
+        {
+            MERGERECT (r2);
+	}
+        while (r2 != r2_end);
+    }
+
+    /* Add current rectangle */
+    NEWRECT (region, next_rect, x1, y1, x2, y2);
+
+    return TRUE;
+}
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX(_intersect_rect) (region_type_t *dest,
+			 region_type_t *source,
+			 int x, int y,
+			 unsigned int width,
+			 unsigned int height)
+{
+    region_type_t region;
+
+    region.data = NULL;
+    region.extents.x1 = x;
+    region.extents.y1 = y;
+    region.extents.x2 = x + width;
+    region.extents.y2 = y + height;
+
+    return PREFIX(_intersect) (dest, source, &region);
+}
+
+/* Convenience function for performing union of region with a
+ * single rectangle
+ */
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_union_rect) (region_type_t *dest,
+                      region_type_t *source,
+                      int            x,
+		      int            y,
+                      unsigned int   width,
+		      unsigned int   height)
+{
+    region_type_t region;
+
+    region.extents.x1 = x;
+    region.extents.y1 = y;
+    region.extents.x2 = x + width;
+    region.extents.y2 = y + height;
+
+    if (!GOOD_RECT (&region.extents))
+    {
+        if (BAD_RECT (&region.extents))
+            _pixman_log_error (FUNC, "Invalid rectangle passed");
+	return PREFIX (_copy) (dest, source);
+    }
+
+    region.data = NULL;
+
+    return PREFIX (_union) (dest, source, &region);
+}
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_union) (region_type_t *new_reg,
+                 region_type_t *reg1,
+                 region_type_t *reg2)
+{
+    int overlap; /* result ignored */
+
+    /* Return TRUE if some overlap
+     * between reg1, reg2
+     */
+    GOOD (reg1);
+    GOOD (reg2);
+    GOOD (new_reg);
+
+    /*  checks all the simple cases */
+
+    /*
+     * Region 1 and 2 are the same
+     */
+    if (reg1 == reg2)
+        return PREFIX (_copy) (new_reg, reg1);
+
+    /*
+     * Region 1 is empty
+     */
+    if (PIXREGION_NIL (reg1))
+    {
+        if (PIXREGION_NAR (reg1))
+	    return pixman_break (new_reg);
+
+        if (new_reg != reg2)
+	    return PREFIX (_copy) (new_reg, reg2);
+
+	return TRUE;
+    }
+
+    /*
+     * Region 2 is empty
+     */
+    if (PIXREGION_NIL (reg2))
+    {
+        if (PIXREGION_NAR (reg2))
+	    return pixman_break (new_reg);
+
+	if (new_reg != reg1)
+	    return PREFIX (_copy) (new_reg, reg1);
+
+	return TRUE;
+    }
+
+    /*
+     * Region 1 completely subsumes region 2
+     */
+    if (!reg1->data && SUBSUMES (&reg1->extents, &reg2->extents))
+    {
+        if (new_reg != reg1)
+	    return PREFIX (_copy) (new_reg, reg1);
+
+	return TRUE;
+    }
+
+    /*
+     * Region 2 completely subsumes region 1
+     */
+    if (!reg2->data && SUBSUMES (&reg2->extents, &reg1->extents))
+    {
+        if (new_reg != reg2)
+	    return PREFIX (_copy) (new_reg, reg2);
+
+	return TRUE;
+    }
+
+    if (!pixman_op (new_reg, reg1, reg2, pixman_region_union_o, TRUE, TRUE, &overlap))
+	return FALSE;
+
+    new_reg->extents.x1 = MIN (reg1->extents.x1, reg2->extents.x1);
+    new_reg->extents.y1 = MIN (reg1->extents.y1, reg2->extents.y1);
+    new_reg->extents.x2 = MAX (reg1->extents.x2, reg2->extents.x2);
+    new_reg->extents.y2 = MAX (reg1->extents.y2, reg2->extents.y2);
+    
+    GOOD (new_reg);
+
+    return TRUE;
+}
+
+/*======================================================================
+ *	    Batch Rectangle Union
+ *====================================================================*/
+
+#define EXCHANGE_RECTS(a, b)	\
+    {                           \
+        box_type_t t;		\
+        t = rects[a];           \
+        rects[a] = rects[b];    \
+        rects[b] = t;           \
+    }
+
+static void
+quick_sort_rects (
+    box_type_t rects[],
+    int        numRects)
+{
+    int y1;
+    int x1;
+    int i, j;
+    box_type_t *r;
+
+    /* Always called with numRects > 1 */
+
+    do
+    {
+        if (numRects == 2)
+        {
+            if (rects[0].y1 > rects[1].y1 ||
+                (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
+	    {
+		EXCHANGE_RECTS (0, 1);
+	    }
+
+            return;
+	}
+
+        /* Choose partition element, stick in location 0 */
+        EXCHANGE_RECTS (0, numRects >> 1);
+        y1 = rects[0].y1;
+        x1 = rects[0].x1;
+
+        /* Partition array */
+        i = 0;
+        j = numRects;
+
+        do
+        {
+            r = &(rects[i]);
+            do
+            {
+                r++;
+                i++;
+	    }
+
+            while (i != numRects && (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)))
+		;
+
+	    r = &(rects[j]);
+            do
+            {
+                r--;
+                j--;
+	    }
+            while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
+	    
+            if (i < j)
+		EXCHANGE_RECTS (i, j);
+	}
+        while (i < j);
+
+        /* Move partition element back to middle */
+        EXCHANGE_RECTS (0, j);
+
+        /* Recurse */
+        if (numRects - j - 1 > 1)
+	    quick_sort_rects (&rects[j + 1], numRects - j - 1);
+
+        numRects = j;
+    }
+    while (numRects > 1);
+}
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_validate --
+ *
+ *      Take a ``region'' which is a non-y-x-banded random collection of
+ *      rectangles, and compute a nice region which is the union of all the
+ *      rectangles.
+ *
+ * Results:
+ *	TRUE if successful.
+ *
+ * Side Effects:
+ *      The passed-in ``region'' may be modified.
+ *	overlap set to TRUE if any retangles overlapped,
+ *      else FALSE;
+ *
+ * Strategy:
+ *      Step 1. Sort the rectangles into ascending order with primary key y1
+ *		and secondary key x1.
+ *
+ *      Step 2. Split the rectangles into the minimum number of proper y-x
+ *		banded regions.  This may require horizontally merging
+ *		rectangles, and vertically coalescing bands.  With any luck,
+ *		this step in an identity transformation (ala the Box widget),
+ *		or a coalescing into 1 box (ala Menus).
+ *
+ *	Step 3. Merge the separate regions down to a single region by calling
+ *		pixman_region_union.  Maximize the work each pixman_region_union call does by using
+ *		a binary merge.
+ *
+ *-----------------------------------------------------------------------
+ */
+
+static pixman_bool_t
+validate (region_type_t * badreg,
+          int *           overlap)
+{
+    /* Descriptor for regions under construction  in Step 2. */
+    typedef struct
+    {
+        region_type_t reg;
+        int prev_band;
+        int cur_band;
+    } region_info_t;
+
+    region_info_t stack_regions[64];
+
+    int numRects;                   /* Original numRects for badreg	    */
+    region_info_t *ri;              /* Array of current regions		    */
+    int num_ri;                     /* Number of entries used in ri	    */
+    int size_ri;                    /* Number of entries available in ri    */
+    int i;                          /* Index into rects			    */
+    int j;                          /* Index into ri			    */
+    region_info_t *rit;             /* &ri[j]				    */
+    region_type_t *reg;             /* ri[j].reg			    */
+    box_type_t *box;                /* Current box in rects		    */
+    box_type_t *ri_box;             /* Last box in ri[j].reg		    */
+    region_type_t *hreg;            /* ri[j_half].reg			    */
+    pixman_bool_t ret = TRUE;
+
+    *overlap = FALSE;
+    if (!badreg->data)
+    {
+        GOOD (badreg);
+        return TRUE;
+    }
+    
+    numRects = badreg->data->numRects;
+    if (!numRects)
+    {
+        if (PIXREGION_NAR (badreg))
+	    return FALSE;
+        GOOD (badreg);
+        return TRUE;
+    }
+    
+    if (badreg->extents.x1 < badreg->extents.x2)
+    {
+        if ((numRects) == 1)
+        {
+            FREE_DATA (badreg);
+            badreg->data = (region_data_type_t *) NULL;
+	}
+        else
+        {
+            DOWNSIZE (badreg, numRects);
+	}
+
+        GOOD (badreg);
+
+	return TRUE;
+    }
+
+    /* Step 1: Sort the rects array into ascending (y1, x1) order */
+    quick_sort_rects (PIXREGION_BOXPTR (badreg), numRects);
+
+    /* Step 2: Scatter the sorted array into the minimum number of regions */
+
+    /* Set up the first region to be the first rectangle in badreg */
+    /* Note that step 2 code will never overflow the ri[0].reg rects array */
+    ri = stack_regions;
+    size_ri = sizeof (stack_regions) / sizeof (stack_regions[0]);
+    num_ri = 1;
+    ri[0].prev_band = 0;
+    ri[0].cur_band = 0;
+    ri[0].reg = *badreg;
+    box = PIXREGION_BOXPTR (&ri[0].reg);
+    ri[0].reg.extents = *box;
+    ri[0].reg.data->numRects = 1;
+    badreg->extents = *pixman_region_empty_box;
+    badreg->data = pixman_region_empty_data;
+
+    /* Now scatter rectangles into the minimum set of valid regions.  If the
+     * next rectangle to be added to a region would force an existing rectangle
+     * in the region to be split up in order to maintain y-x banding, just
+     * forget it.  Try the next region.  If it doesn't fit cleanly into any
+     * region, make a new one.
+     */
+
+    for (i = numRects; --i > 0;)
+    {
+        box++;
+        /* Look for a region to append box to */
+        for (j = num_ri, rit = ri; --j >= 0; rit++)
+        {
+            reg = &rit->reg;
+            ri_box = PIXREGION_END (reg);
+
+            if (box->y1 == ri_box->y1 && box->y2 == ri_box->y2)
+            {
+                /* box is in same band as ri_box.  Merge or append it */
+                if (box->x1 <= ri_box->x2)
+                {
+                    /* Merge it with ri_box */
+                    if (box->x1 < ri_box->x2)
+			*overlap = TRUE;
+
+                    if (box->x2 > ri_box->x2)
+			ri_box->x2 = box->x2;
+		}
+                else
+                {
+                    RECTALLOC_BAIL (reg, 1, bail);
+                    *PIXREGION_TOP (reg) = *box;
+                    reg->data->numRects++;
+		}
+		
+                goto next_rect;   /* So sue me */
+	    }
+            else if (box->y1 >= ri_box->y2)
+            {
+                /* Put box into new band */
+                if (reg->extents.x2 < ri_box->x2)
+		    reg->extents.x2 = ri_box->x2;
+		
+                if (reg->extents.x1 > box->x1)
+		    reg->extents.x1 = box->x1;
+		
+                COALESCE (reg, rit->prev_band, rit->cur_band);
+                rit->cur_band = reg->data->numRects;
+                RECTALLOC_BAIL (reg, 1, bail);
+                *PIXREGION_TOP (reg) = *box;
+                reg->data->numRects++;
+
+                goto next_rect;
+	    }
+            /* Well, this region was inappropriate.  Try the next one. */
+	} /* for j */
+
+        /* Uh-oh.  No regions were appropriate.  Create a new one. */
+        if (size_ri == num_ri)
+        {
+            size_t data_size;
+
+            /* Oops, allocate space for new region information */
+            size_ri <<= 1;
+
+            data_size = size_ri * sizeof(region_info_t);
+            if (data_size / size_ri != sizeof(region_info_t))
+		goto bail;
+
+            if (ri == stack_regions)
+            {
+                rit = malloc (data_size);
+                if (!rit)
+		    goto bail;
+                memcpy (rit, ri, num_ri * sizeof (region_info_t));
+	    }
+            else
+            {
+                rit = (region_info_t *) realloc (ri, data_size);
+                if (!rit)
+		    goto bail;
+	    }
+            ri = rit;
+            rit = &ri[num_ri];
+	}
+        num_ri++;
+        rit->prev_band = 0;
+        rit->cur_band = 0;
+        rit->reg.extents = *box;
+        rit->reg.data = (region_data_type_t *)NULL;
+
+	/* MUST force allocation */
+        if (!pixman_rect_alloc (&rit->reg, (i + num_ri) / num_ri))
+	    goto bail;
+	
+    next_rect: ;
+    } /* for i */
+
+    /* Make a final pass over each region in order to COALESCE and set
+     * extents.x2 and extents.y2
+     */
+    for (j = num_ri, rit = ri; --j >= 0; rit++)
+    {
+        reg = &rit->reg;
+        ri_box = PIXREGION_END (reg);
+        reg->extents.y2 = ri_box->y2;
+
+        if (reg->extents.x2 < ri_box->x2)
+	    reg->extents.x2 = ri_box->x2;
+	
+        COALESCE (reg, rit->prev_band, rit->cur_band);
+
+	if (reg->data->numRects == 1) /* keep unions happy below */
+        {
+            FREE_DATA (reg);
+            reg->data = (region_data_type_t *)NULL;
+	}
+    }
+
+    /* Step 3: Union all regions into a single region */
+    while (num_ri > 1)
+    {
+        int half = num_ri / 2;
+        for (j = num_ri & 1; j < (half + (num_ri & 1)); j++)
+        {
+            reg = &ri[j].reg;
+            hreg = &ri[j + half].reg;
+
+            if (!pixman_op (reg, reg, hreg, pixman_region_union_o, TRUE, TRUE, overlap))
+		ret = FALSE;
+
+            if (hreg->extents.x1 < reg->extents.x1)
+		reg->extents.x1 = hreg->extents.x1;
+
+            if (hreg->extents.y1 < reg->extents.y1)
+		reg->extents.y1 = hreg->extents.y1;
+
+            if (hreg->extents.x2 > reg->extents.x2)
+		reg->extents.x2 = hreg->extents.x2;
+
+            if (hreg->extents.y2 > reg->extents.y2)
+		reg->extents.y2 = hreg->extents.y2;
+
+            FREE_DATA (hreg);
+	}
+
+        num_ri -= half;
+
+	if (!ret)
+	    goto bail;
+    }
+
+    *badreg = ri[0].reg;
+
+    if (ri != stack_regions)
+	free (ri);
+
+    GOOD (badreg);
+    return ret;
+
+bail:
+    for (i = 0; i < num_ri; i++)
+	FREE_DATA (&ri[i].reg);
+
+    if (ri != stack_regions)
+	free (ri);
+
+    return pixman_break (badreg);
+}
+
+/*======================================================================
+ *                Region Subtraction
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_subtract_o --
+ *	Overlapping band subtraction. x1 is the left-most point not yet
+ *	checked.
+ *
+ * Results:
+ *	TRUE if successful.
+ *
+ * Side Effects:
+ *	region may have rectangles added to it.
+ *
+ *-----------------------------------------------------------------------
+ */
+/*ARGSUSED*/
+static pixman_bool_t
+pixman_region_subtract_o (region_type_t * region,
+			  box_type_t *    r1,
+			  box_type_t *    r1_end,
+			  box_type_t *    r2,
+			  box_type_t *    r2_end,
+			  int             y1,
+			  int             y2,
+			  int *           overlap)
+{
+    box_type_t *        next_rect;
+    int x1;
+
+    x1 = r1->x1;
+
+    critical_if_fail (y1 < y2);
+    critical_if_fail (r1 != r1_end && r2 != r2_end);
+
+    next_rect = PIXREGION_TOP (region);
+
+    do
+    {
+        if (r2->x2 <= x1)
+        {
+            /*
+	     * Subtrahend entirely to left of minuend: go to next subtrahend.
+	     */
+            r2++;
+	}
+        else if (r2->x1 <= x1)
+        {
+            /*
+	     * Subtrahend preceeds minuend: nuke left edge of minuend.
+	     */
+            x1 = r2->x2;
+            if (x1 >= r1->x2)
+            {
+                /*
+		 * Minuend completely covered: advance to next minuend and
+		 * reset left fence to edge of new minuend.
+		 */
+                r1++;
+                if (r1 != r1_end)
+		    x1 = r1->x1;
+	    }
+            else
+            {
+                /*
+		 * Subtrahend now used up since it doesn't extend beyond
+		 * minuend
+		 */
+                r2++;
+	    }
+	}
+        else if (r2->x1 < r1->x2)
+        {
+            /*
+	     * Left part of subtrahend covers part of minuend: add uncovered
+	     * part of minuend to region and skip to next subtrahend.
+	     */
+            critical_if_fail (x1 < r2->x1);
+            NEWRECT (region, next_rect, x1, y1, r2->x1, y2);
+
+            x1 = r2->x2;
+            if (x1 >= r1->x2)
+            {
+                /*
+		 * Minuend used up: advance to new...
+		 */
+                r1++;
+                if (r1 != r1_end)
+		    x1 = r1->x1;
+	    }
+            else
+            {
+                /*
+		 * Subtrahend used up
+		 */
+                r2++;
+	    }
+	}
+        else
+        {
+            /*
+	     * Minuend used up: add any remaining piece before advancing.
+	     */
+            if (r1->x2 > x1)
+		NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
+
+            r1++;
+
+	    if (r1 != r1_end)
+		x1 = r1->x1;
+	}
+    }
+    while ((r1 != r1_end) && (r2 != r2_end));
+
+    /*
+     * Add remaining minuend rectangles to region.
+     */
+    while (r1 != r1_end)
+    {
+        critical_if_fail (x1 < r1->x2);
+
+        NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
+
+        r1++;
+        if (r1 != r1_end)
+	    x1 = r1->x1;
+    }
+    return TRUE;
+}
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_subtract --
+ *	Subtract reg_s from reg_m and leave the result in reg_d.
+ *	S stands for subtrahend, M for minuend and D for difference.
+ *
+ * Results:
+ *	TRUE if successful.
+ *
+ * Side Effects:
+ *	reg_d is overwritten.
+ *
+ *-----------------------------------------------------------------------
+ */
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_subtract) (region_type_t *reg_d,
+                    region_type_t *reg_m,
+                    region_type_t *reg_s)
+{
+    int overlap; /* result ignored */
+
+    GOOD (reg_m);
+    GOOD (reg_s);
+    GOOD (reg_d);
+    
+    /* check for trivial rejects */
+    if (PIXREGION_NIL (reg_m) || PIXREGION_NIL (reg_s) ||
+        !EXTENTCHECK (&reg_m->extents, &reg_s->extents))
+    {
+        if (PIXREGION_NAR (reg_s))
+	    return pixman_break (reg_d);
+	
+        return PREFIX (_copy) (reg_d, reg_m);
+    }
+    else if (reg_m == reg_s)
+    {
+        FREE_DATA (reg_d);
+        reg_d->extents.x2 = reg_d->extents.x1;
+        reg_d->extents.y2 = reg_d->extents.y1;
+        reg_d->data = pixman_region_empty_data;
+
+        return TRUE;
+    }
+
+    /* Add those rectangles in region 1 that aren't in region 2,
+       do yucky substraction for overlaps, and
+       just throw away rectangles in region 2 that aren't in region 1 */
+    if (!pixman_op (reg_d, reg_m, reg_s, pixman_region_subtract_o, TRUE, FALSE, &overlap))
+	return FALSE;
+
+    /*
+     * Can't alter reg_d's extents before we call pixman_op because
+     * it might be one of the source regions and pixman_op depends
+     * on the extents of those regions being unaltered. Besides, this
+     * way there's no checking against rectangles that will be nuked
+     * due to coalescing, so we have to examine fewer rectangles.
+     */
+    pixman_set_extents (reg_d);
+    GOOD (reg_d);
+    return TRUE;
+}
+
+/*======================================================================
+ *	    Region Inversion
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_inverse --
+ *	Take a region and a box and return a region that is everything
+ *	in the box but not in the region. The careful reader will note
+ *	that this is the same as subtracting the region from the box...
+ *
+ * Results:
+ *	TRUE.
+ *
+ * Side Effects:
+ *	new_reg is overwritten.
+ *
+ *-----------------------------------------------------------------------
+ */
+pixman_bool_t
+PIXMAN_EXPORT PREFIX (_inverse) (region_type_t *new_reg,  /* Destination region */
+                                 region_type_t *reg1,     /* Region to invert */
+                                 box_type_t *   inv_rect) /* Bounding box for inversion */
+{
+    region_type_t inv_reg; /* Quick and dirty region made from the
+			    * bounding box */
+    int overlap;           /* result ignored */
+
+    GOOD (reg1);
+    GOOD (new_reg);
+    
+    /* check for trivial rejects */
+    if (PIXREGION_NIL (reg1) || !EXTENTCHECK (inv_rect, &reg1->extents))
+    {
+        if (PIXREGION_NAR (reg1))
+	    return pixman_break (new_reg);
+	
+        new_reg->extents = *inv_rect;
+        FREE_DATA (new_reg);
+        new_reg->data = (region_data_type_t *)NULL;
+	
+        return TRUE;
+    }
+
+    /* Add those rectangles in region 1 that aren't in region 2,
+     * do yucky substraction for overlaps, and
+     * just throw away rectangles in region 2 that aren't in region 1
+     */
+    inv_reg.extents = *inv_rect;
+    inv_reg.data = (region_data_type_t *)NULL;
+    if (!pixman_op (new_reg, &inv_reg, reg1, pixman_region_subtract_o, TRUE, FALSE, &overlap))
+	return FALSE;
+
+    /*
+     * Can't alter new_reg's extents before we call pixman_op because
+     * it might be one of the source regions and pixman_op depends
+     * on the extents of those regions being unaltered. Besides, this
+     * way there's no checking against rectangles that will be nuked
+     * due to coalescing, so we have to examine fewer rectangles.
+     */
+    pixman_set_extents (new_reg);
+    GOOD (new_reg);
+    return TRUE;
+}
+
+/*
+ *   rect_in(region, rect)
+ *   This routine takes a pointer to a region and a pointer to a box
+ *   and determines if the box is outside/inside/partly inside the region.
+ *
+ *   The idea is to travel through the list of rectangles trying to cover the
+ *   passed box with them. Anytime a piece of the rectangle isn't covered
+ *   by a band of rectangles, part_out is set TRUE. Any time a rectangle in
+ *   the region covers part of the box, part_in is set TRUE. The process ends
+ *   when either the box has been completely covered (we reached a band that
+ *   doesn't overlap the box, part_in is TRUE and part_out is false), the
+ *   box has been partially covered (part_in == part_out == TRUE -- because of
+ *   the banding, the first time this is true we know the box is only
+ *   partially in the region) or is outside the region (we reached a band
+ *   that doesn't overlap the box at all and part_in is false)
+ */
+
+pixman_region_overlap_t
+PIXMAN_EXPORT PREFIX (_contains_rectangle) (region_type_t *  region,
+                                            box_type_t *     prect)
+{
+    box_type_t *     pbox;
+    box_type_t *     pbox_end;
+    int part_in, part_out;
+    int numRects;
+    int x, y;
+
+    GOOD (region);
+
+    numRects = PIXREGION_NUMRECTS (region);
+
+    /* useful optimization */
+    if (!numRects || !EXTENTCHECK (&region->extents, prect))
+	return(PIXMAN_REGION_OUT);
+
+    if (numRects == 1)
+    {
+        /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
+        if (SUBSUMES (&region->extents, prect))
+	    return(PIXMAN_REGION_IN);
+        else
+	    return(PIXMAN_REGION_PART);
+    }
+
+    part_out = FALSE;
+    part_in = FALSE;
+
+    /* (x,y) starts at upper left of rect, moving to the right and down */
+    x = prect->x1;
+    y = prect->y1;
+
+    /* can stop when both part_out and part_in are TRUE, or we reach prect->y2 */
+    for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;
+         pbox != pbox_end;
+         pbox++)
+    {
+
+        if (pbox->y2 <= y)
+	    continue;   /* getting up to speed or skipping remainder of band */
+
+        if (pbox->y1 > y)
+        {
+            part_out = TRUE;     /* missed part of rectangle above */
+            if (part_in || (pbox->y1 >= prect->y2))
+		break;
+            y = pbox->y1;       /* x guaranteed to be == prect->x1 */
+	}
+
+        if (pbox->x2 <= x)
+	    continue;           /* not far enough over yet */
+
+        if (pbox->x1 > x)
+        {
+            part_out = TRUE;     /* missed part of rectangle to left */
+            if (part_in)
+		break;
+	}
+
+        if (pbox->x1 < prect->x2)
+        {
+            part_in = TRUE;      /* definitely overlap */
+            if (part_out)
+		break;
+	}
+
+        if (pbox->x2 >= prect->x2)
+        {
+            y = pbox->y2;       /* finished with this band */
+            if (y >= prect->y2)
+		break;
+            x = prect->x1;      /* reset x out to left again */
+	}
+        else
+        {
+            /*
+	     * Because boxes in a band are maximal width, if the first box
+	     * to overlap the rectangle doesn't completely cover it in that
+	     * band, the rectangle must be partially out, since some of it
+	     * will be uncovered in that band. part_in will have been set true
+	     * by now...
+	     */
+            part_out = TRUE;
+            break;
+	}
+    }
+
+    if (part_in)
+    {
+        if (y < prect->y2)
+	    return PIXMAN_REGION_PART;
+        else
+	    return PIXMAN_REGION_IN;
+    }
+    else
+    {
+        return PIXMAN_REGION_OUT;
+    }
+}
+
+/* PREFIX(_translate) (region, x, y)
+ * translates in place
+ */
+
+PIXMAN_EXPORT void
+PREFIX (_translate) (region_type_t *region, int x, int y)
+{
+    overflow_int_t x1, x2, y1, y2;
+    int nbox;
+    box_type_t * pbox;
+
+    GOOD (region);
+    region->extents.x1 = x1 = region->extents.x1 + x;
+    region->extents.y1 = y1 = region->extents.y1 + y;
+    region->extents.x2 = x2 = region->extents.x2 + x;
+    region->extents.y2 = y2 = region->extents.y2 + y;
+    
+    if (((x1 - PIXMAN_REGION_MIN) | (y1 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x2) | (PIXMAN_REGION_MAX - y2)) >= 0)
+    {
+        if (region->data && (nbox = region->data->numRects))
+        {
+            for (pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
+            {
+                pbox->x1 += x;
+                pbox->y1 += y;
+                pbox->x2 += x;
+                pbox->y2 += y;
+	    }
+	}
+        return;
+    }
+
+    if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)
+    {
+        region->extents.x2 = region->extents.x1;
+        region->extents.y2 = region->extents.y1;
+        FREE_DATA (region);
+        region->data = pixman_region_empty_data;
+        return;
+    }
+
+    if (x1 < PIXMAN_REGION_MIN)
+	region->extents.x1 = PIXMAN_REGION_MIN;
+    else if (x2 > PIXMAN_REGION_MAX)
+	region->extents.x2 = PIXMAN_REGION_MAX;
+
+    if (y1 < PIXMAN_REGION_MIN)
+	region->extents.y1 = PIXMAN_REGION_MIN;
+    else if (y2 > PIXMAN_REGION_MAX)
+	region->extents.y2 = PIXMAN_REGION_MAX;
+
+    if (region->data && (nbox = region->data->numRects))
+    {
+        box_type_t * pbox_out;
+
+        for (pbox_out = pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
+        {
+            pbox_out->x1 = x1 = pbox->x1 + x;
+            pbox_out->y1 = y1 = pbox->y1 + y;
+            pbox_out->x2 = x2 = pbox->x2 + x;
+            pbox_out->y2 = y2 = pbox->y2 + y;
+
+            if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) |
+                 (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)
+            {
+                region->data->numRects--;
+                continue;
+	    }
+
+            if (x1 < PIXMAN_REGION_MIN)
+		pbox_out->x1 = PIXMAN_REGION_MIN;
+            else if (x2 > PIXMAN_REGION_MAX)
+		pbox_out->x2 = PIXMAN_REGION_MAX;
+
+            if (y1 < PIXMAN_REGION_MIN)
+		pbox_out->y1 = PIXMAN_REGION_MIN;
+            else if (y2 > PIXMAN_REGION_MAX)
+		pbox_out->y2 = PIXMAN_REGION_MAX;
+
+            pbox_out++;
+	}
+
+        if (pbox_out != pbox)
+        {
+            if (region->data->numRects == 1)
+            {
+                region->extents = *PIXREGION_BOXPTR (region);
+                FREE_DATA (region);
+                region->data = (region_data_type_t *)NULL;
+	    }
+            else
+	    {
+		pixman_set_extents (region);
+	    }
+	}
+    }
+
+    GOOD (region);
+}
+
+PIXMAN_EXPORT void
+PREFIX (_reset) (region_type_t *region, box_type_t *box)
+{
+    GOOD (region);
+
+    critical_if_fail (GOOD_RECT (box));
+
+    region->extents = *box;
+
+    FREE_DATA (region);
+
+    region->data = NULL;
+}
+
+/* box is "return" value */
+PIXMAN_EXPORT int
+PREFIX (_contains_point) (region_type_t * region,
+                          int x, int y,
+                          box_type_t * box)
+{
+    box_type_t *pbox, *pbox_end;
+    int numRects;
+
+    GOOD (region);
+    numRects = PIXREGION_NUMRECTS (region);
+
+    if (!numRects || !INBOX (&region->extents, x, y))
+	return(FALSE);
+
+    if (numRects == 1)
+    {
+        if (box)
+	    *box = region->extents;
+
+        return(TRUE);
+    }
+
+    for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;
+	 pbox != pbox_end;
+	 pbox++)
+    {
+        if (y >= pbox->y2)
+	    continue;           /* not there yet */
+
+        if ((y < pbox->y1) || (x < pbox->x1))
+	    break;              /* missed it */
+
+        if (x >= pbox->x2)
+	    continue;           /* not there yet */
+
+        if (box)
+	    *box = *pbox;
+
+        return(TRUE);
+    }
+
+    return(FALSE);
+}
+
+PIXMAN_EXPORT int
+PREFIX (_not_empty) (region_type_t * region)
+{
+    GOOD (region);
+
+    return(!PIXREGION_NIL (region));
+}
+
+PIXMAN_EXPORT box_type_t *
+PREFIX (_extents) (region_type_t * region)
+{
+    GOOD (region);
+
+    return(&region->extents);
+}
+
+/*
+ * Clip a list of scanlines to a region.  The caller has allocated the
+ * space.  FSorted is non-zero if the scanline origins are in ascending order.
+ *
+ * returns the number of new, clipped scanlines.
+ */
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_selfcheck) (region_type_t *reg)
+{
+    int i, numRects;
+
+    if ((reg->extents.x1 > reg->extents.x2) ||
+        (reg->extents.y1 > reg->extents.y2))
+    {
+	return FALSE;
+    }
+
+    numRects = PIXREGION_NUMRECTS (reg);
+    if (!numRects)
+    {
+	return ((reg->extents.x1 == reg->extents.x2) &&
+	        (reg->extents.y1 == reg->extents.y2) &&
+	        (reg->data->size || (reg->data == pixman_region_empty_data)));
+    }
+    else if (numRects == 1)
+    {
+	return (!reg->data);
+    }
+    else
+    {
+        box_type_t * pbox_p, * pbox_n;
+        box_type_t box;
+
+        pbox_p = PIXREGION_RECTS (reg);
+        box = *pbox_p;
+        box.y2 = pbox_p[numRects - 1].y2;
+        pbox_n = pbox_p + 1;
+
+        for (i = numRects; --i > 0; pbox_p++, pbox_n++)
+        {
+            if ((pbox_n->x1 >= pbox_n->x2) ||
+                (pbox_n->y1 >= pbox_n->y2))
+	    {
+		return FALSE;
+	    }
+
+            if (pbox_n->x1 < box.x1)
+		box.x1 = pbox_n->x1;
+	    
+            if (pbox_n->x2 > box.x2)
+		box.x2 = pbox_n->x2;
+	    
+            if ((pbox_n->y1 < pbox_p->y1) ||
+                ((pbox_n->y1 == pbox_p->y1) &&
+                 ((pbox_n->x1 < pbox_p->x2) || (pbox_n->y2 != pbox_p->y2))))
+	    {
+		return FALSE;
+	    }
+	}
+
+        return ((box.x1 == reg->extents.x1) &&
+                (box.x2 == reg->extents.x2) &&
+                (box.y1 == reg->extents.y1) &&
+                (box.y2 == reg->extents.y2));
+    }
+}
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_init_rects) (region_type_t *region,
+                      const box_type_t *boxes, int count)
+{
+    box_type_t *rects;
+    int displacement;
+    int i;
+
+    /* if it's 1, then we just want to set the extents, so call
+     * the existing method. */
+    if (count == 1)
+    {
+        PREFIX (_init_rect) (region,
+                             boxes[0].x1,
+                             boxes[0].y1,
+                             boxes[0].x2 - boxes[0].x1,
+                             boxes[0].y2 - boxes[0].y1);
+        return TRUE;
+    }
+
+    PREFIX (_init) (region);
+
+    /* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is
+     * a special case, and causing pixman_rect_alloc would cause
+     * us to leak memory (because the 0-rect case should be the
+     * static pixman_region_empty_data data).
+     */
+    if (count == 0)
+	return TRUE;
+
+    if (!pixman_rect_alloc (region, count))
+	return FALSE;
+
+    rects = PIXREGION_RECTS (region);
+
+    /* Copy in the rects */
+    memcpy (rects, boxes, sizeof(box_type_t) * count);
+    region->data->numRects = count;
+
+    /* Eliminate empty and malformed rectangles */
+    displacement = 0;
+
+    for (i = 0; i < count; ++i)
+    {
+        box_type_t *box = &rects[i];
+
+        if (box->x1 >= box->x2 || box->y1 >= box->y2)
+	    displacement++;
+        else if (displacement)
+	    rects[i - displacement] = rects[i];
+    }
+
+    region->data->numRects -= displacement;
+
+    /* If eliminating empty rectangles caused there
+     * to be only 0 or 1 rectangles, deal with that.
+     */
+    if (region->data->numRects == 0)
+    {
+        FREE_DATA (region);
+        PREFIX (_init) (region);
+
+        return TRUE;
+    }
+
+    if (region->data->numRects == 1)
+    {
+        region->extents = rects[0];
+
+        FREE_DATA (region);
+        region->data = NULL;
+
+        GOOD (region);
+
+        return TRUE;
+    }
+
+    /* Validate */
+    region->extents.x1 = region->extents.x2 = 0;
+
+    return validate (region, &i);
+}
+
+#define READ(_ptr) (*(_ptr))
+
+static inline box_type_t *
+bitmap_addrect (region_type_t *reg,
+                box_type_t *r,
+                box_type_t **first_rect,
+                int rx1, int ry1,
+                int rx2, int ry2)
+{
+    if ((rx1 < rx2) && (ry1 < ry2) &&
+	(!(reg->data->numRects &&
+	   ((r-1)->y1 == ry1) && ((r-1)->y2 == ry2) &&
+	   ((r-1)->x1 <= rx1) && ((r-1)->x2 >= rx2))))
+    {
+	if (reg->data->numRects == reg->data->size)
+	{
+	    if (!pixman_rect_alloc (reg, 1))
+		return NULL;
+	    *first_rect = PIXREGION_BOXPTR(reg);
+	    r = *first_rect + reg->data->numRects;
+	}
+	r->x1 = rx1;
+	r->y1 = ry1;
+	r->x2 = rx2;
+	r->y2 = ry2;
+	reg->data->numRects++;
+	if (r->x1 < reg->extents.x1)
+	    reg->extents.x1 = r->x1;
+	if (r->x2 > reg->extents.x2)
+	    reg->extents.x2 = r->x2;
+	r++;
+    }
+    return r;
+}
+
+/* Convert bitmap clip mask into clipping region.
+ * First, goes through each line and makes boxes by noting the transitions
+ * from 0 to 1 and 1 to 0.
+ * Then it coalesces the current line with the previous if they have boxes
+ * at the same X coordinates.
+ * Stride is in number of uint32_t per line.
+ */
+PIXMAN_EXPORT void
+PREFIX (_init_from_image) (region_type_t *region,
+                           pixman_image_t *image)
+{
+    uint32_t mask0 = 0xffffffff & ~SCREEN_SHIFT_RIGHT(0xffffffff, 1);
+    box_type_t *first_rect, *rects, *prect_line_start;
+    box_type_t *old_rect, *new_rect;
+    uint32_t *pw, w, *pw_line, *pw_line_end;
+    int	irect_prev_start, irect_line_start;
+    int	h, base, rx1 = 0, crects;
+    int	ib;
+    pixman_bool_t in_box, same;
+    int width, height, stride;
+
+    PREFIX(_init) (region);
+
+    critical_if_fail (region->data);
+
+    return_if_fail (image->type == BITS);
+    return_if_fail (image->bits.format == PIXMAN_a1);
+
+    pw_line = pixman_image_get_data (image);
+    width = pixman_image_get_width (image);
+    height = pixman_image_get_height (image);
+    stride = pixman_image_get_stride (image) / 4;
+
+    first_rect = PIXREGION_BOXPTR(region);
+    rects = first_rect;
+
+    region->extents.x1 = width - 1;
+    region->extents.x2 = 0;
+    irect_prev_start = -1;
+    for (h = 0; h < height; h++)
+    {
+        pw = pw_line;
+        pw_line += stride;
+        irect_line_start = rects - first_rect;
+
+        /* If the Screen left most bit of the word is set, we're starting in
+         * a box */
+        if (READ(pw) & mask0)
+        {
+            in_box = TRUE;
+            rx1 = 0;
+        }
+        else
+        {
+            in_box = FALSE;
+        }
+
+        /* Process all words which are fully in the pixmap */
+        pw_line_end = pw + (width >> 5);
+        for (base = 0; pw < pw_line_end; base += 32)
+        {
+            w = READ(pw++);
+            if (in_box)
+            {
+                if (!~w)
+                    continue;
+            }
+            else
+            {
+                if (!w)
+                    continue;
+            }
+            for (ib = 0; ib < 32; ib++)
+            {
+                /* If the Screen left most bit of the word is set, we're
+                 * starting a box */
+                if (w & mask0)
+                {
+                    if (!in_box)
+                    {
+                        rx1 = base + ib;
+                        /* start new box */
+                        in_box = TRUE;
+                    }
+                }
+                else
+                {
+                    if (in_box)
+                    {
+                        /* end box */
+                        rects = bitmap_addrect (region, rects, &first_rect,
+                                                rx1, h, base + ib, h + 1);
+                        if (rects == NULL)
+                            goto error;
+                        in_box = FALSE;
+                    }
+                }
+                /* Shift the word VISUALLY left one. */
+                w = SCREEN_SHIFT_LEFT(w, 1);
+            }
+        }
+
+        if (width & 31)
+        {
+            /* Process final partial word on line */
+             w = READ(pw++);
+            for (ib = 0; ib < (width & 31); ib++)
+            {
+                /* If the Screen left most bit of the word is set, we're
+                 * starting a box */
+                if (w & mask0)
+                {
+                    if (!in_box)
+                    {
+                        rx1 = base + ib;
+                        /* start new box */
+                        in_box = TRUE;
+                    }
+                }
+                else
+                {
+                    if (in_box)
+                    {
+                        /* end box */
+                        rects = bitmap_addrect(region, rects, &first_rect,
+					       rx1, h, base + ib, h + 1);
+			if (rects == NULL)
+			    goto error;
+                        in_box = FALSE;
+                    }
+                }
+                /* Shift the word VISUALLY left one. */
+                w = SCREEN_SHIFT_LEFT(w, 1);
+            }
+        }
+        /* If scanline ended with last bit set, end the box */
+        if (in_box)
+        {
+            rects = bitmap_addrect(region, rects, &first_rect,
+				   rx1, h, base + (width & 31), h + 1);
+	    if (rects == NULL)
+		goto error;
+        }
+        /* if all rectangles on this line have the same x-coords as
+         * those on the previous line, then add 1 to all the previous  y2s and
+         * throw away all the rectangles from this line
+         */
+        same = FALSE;
+        if (irect_prev_start != -1)
+        {
+            crects = irect_line_start - irect_prev_start;
+            if (crects != 0 &&
+                crects == ((rects - first_rect) - irect_line_start))
+            {
+                old_rect = first_rect + irect_prev_start;
+                new_rect = prect_line_start = first_rect + irect_line_start;
+                same = TRUE;
+                while (old_rect < prect_line_start)
+                {
+                    if ((old_rect->x1 != new_rect->x1) ||
+                        (old_rect->x2 != new_rect->x2))
+                    {
+                          same = FALSE;
+                          break;
+                    }
+                    old_rect++;
+                    new_rect++;
+                }
+                if (same)
+                {
+                    old_rect = first_rect + irect_prev_start;
+                    while (old_rect < prect_line_start)
+                    {
+                        old_rect->y2 += 1;
+                        old_rect++;
+                    }
+                    rects -= crects;
+                    region->data->numRects -= crects;
+                }
+            }
+        }
+        if(!same)
+            irect_prev_start = irect_line_start;
+    }
+    if (!region->data->numRects)
+    {
+        region->extents.x1 = region->extents.x2 = 0;
+    }
+    else
+    {
+        region->extents.y1 = PIXREGION_BOXPTR(region)->y1;
+        region->extents.y2 = PIXREGION_END(region)->y2;
+        if (region->data->numRects == 1)
+        {
+            free (region->data);
+            region->data = NULL;
+        }
+    }
+
+ error:
+    return;
+}