schema_init.c

/* schema_init.c - init builtin schema */
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
 * Copyright 1998-2004 The OpenLDAP Foundation.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted only as authorized by the OpenLDAP
 * Public License.
 *
 * A copy of this license is available in the file LICENSE in the
 * top-level directory of the distribution or, alternatively, at
 * <http://www.OpenLDAP.org/license.html>.
 */

#include "portable.h"

#include <stdio.h>
#include <limits.h>

#include <ac/ctype.h>
#include <ac/errno.h>
#include <ac/string.h>
#include <ac/socket.h>

#include "slap.h"

#include "ldap_utf8.h"

#ifdef HAVE_TLS
#include <openssl/x509.h>
#include <openssl/err.h>
#include <openssl/rsa.h>
#include <openssl/crypto.h>
#include <openssl/pem.h>
#include <openssl/bio.h>
#include <openssl/asn1.h>
#include <openssl/x509v3.h>
#include <openssl/ssl.h>
#endif

#include "lutil_hash.h"
#define HASH_BYTES				LUTIL_HASH_BYTES
#define HASH_CONTEXT			lutil_HASH_CTX
#define HASH_Init(c)			lutil_HASHInit(c)
#define HASH_Update(c,buf,len)	lutil_HASHUpdate(c,buf,len)
#define HASH_Final(d,c)			lutil_HASHFinal(d,c)

#define	OpenLDAPaciMatch			NULL

/* approx matching rules */
#define directoryStringApproxMatchOID	"1.3.6.1.4.1.4203.666.4.4"
#define directoryStringApproxMatch		approxMatch
#define directoryStringApproxIndexer	approxIndexer
#define directoryStringApproxFilter		approxFilter
#define IA5StringApproxMatchOID			"1.3.6.1.4.1.4203.666.4.5"
#define IA5StringApproxMatch			approxMatch
#define IA5StringApproxIndexer			approxIndexer
#define IA5StringApproxFilter			approxFilter

static int
inValidate(
	Syntax *syntax,
	struct berval *in )
{
	/* no value allowed */
	return LDAP_INVALID_SYNTAX;
}

static int
blobValidate(
	Syntax *syntax,
	struct berval *in )
{
	/* any value allowed */
	return LDAP_SUCCESS;
}

#define berValidate blobValidate

static int
sequenceValidate(
	Syntax *syntax,
	struct berval *in )
{
	if ( in->bv_len < 2 ) return LDAP_INVALID_SYNTAX;
	if ( in->bv_val[0] != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;

	return LDAP_SUCCESS;
}


#ifdef HAVE_TLS
static int certificateValidate( Syntax *syntax, struct berval *in )
{
	X509 *xcert=NULL;
	unsigned char *p = (unsigned char *)in->bv_val;
 
	xcert = d2i_X509(NULL, &p, in->bv_len);
	if ( !xcert ) return LDAP_INVALID_SYNTAX;
	X509_free(xcert);
	return LDAP_SUCCESS;
}
#else
#define certificateValidate sequenceValidate
#endif

static int
octetStringMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	struct berval *asserted = (struct berval *) assertedValue;
	int match = value->bv_len - asserted->bv_len;

	if( match == 0 ) {
		match = memcmp( value->bv_val, asserted->bv_val, value->bv_len );
	}

	*matchp = match;
	return LDAP_SUCCESS;
}

static int
octetStringOrderingMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	struct berval *asserted = (struct berval *) assertedValue;
	ber_len_t v_len  = value->bv_len;
	ber_len_t av_len = asserted->bv_len;

	int match = memcmp( value->bv_val, asserted->bv_val,
		(v_len < av_len ? v_len : av_len) );

	if( match == 0 ) match = v_len - av_len;

	*matchp = match;
	return LDAP_SUCCESS;
}

/* Index generation function */
int octetStringIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	BerVarray values,
	BerVarray *keysp,
	void *ctx )
{
	int i;
	size_t slen, mlen;
	BerVarray keys;
	HASH_CONTEXT HASHcontext;
	unsigned char HASHdigest[HASH_BYTES];
	struct berval digest;
	digest.bv_val = (char *)HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

	for( i=0; values[i].bv_val != NULL; i++ ) {
		/* just count them */
	}

	/* we should have at least one value at this point */
	assert( i > 0 );

	keys = slap_sl_malloc( sizeof( struct berval ) * (i+1), ctx );

	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;

	for( i=0; values[i].bv_val != NULL; i++ ) {
		HASH_Init( &HASHcontext );
		if( prefix != NULL && prefix->bv_len > 0 ) {
			HASH_Update( &HASHcontext,
				(unsigned char *)prefix->bv_val,
				prefix->bv_len );
		}
		HASH_Update( &HASHcontext,
			(unsigned char *)syntax->ssyn_oid, slen );
		HASH_Update( &HASHcontext,
			(unsigned char *)mr->smr_oid, mlen );
		HASH_Update( &HASHcontext,
			(unsigned char *)values[i].bv_val, values[i].bv_len );
		HASH_Final( HASHdigest, &HASHcontext );

		ber_dupbv_x( &keys[i], &digest, ctx );
	}

	keys[i].bv_val = NULL;
	keys[i].bv_len = 0;

	*keysp = keys;

	return LDAP_SUCCESS;
}

/* Index generation function */
int octetStringFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertedValue,
	BerVarray *keysp,
	void *ctx )
{
	size_t slen, mlen;
	BerVarray keys;
	HASH_CONTEXT HASHcontext;
	unsigned char HASHdigest[HASH_BYTES];
	struct berval *value = (struct berval *) assertedValue;
	struct berval digest;
	digest.bv_val = (char *)HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;

	keys = slap_sl_malloc( sizeof( struct berval ) * 2, ctx );

	HASH_Init( &HASHcontext );
	if( prefix != NULL && prefix->bv_len > 0 ) {
		HASH_Update( &HASHcontext,
			(unsigned char *)prefix->bv_val, prefix->bv_len );
	}
	HASH_Update( &HASHcontext,
		(unsigned char *)syntax->ssyn_oid, slen );
	HASH_Update( &HASHcontext,
		(unsigned char *)mr->smr_oid, mlen );
	HASH_Update( &HASHcontext,
		(unsigned char *)value->bv_val, value->bv_len );
	HASH_Final( HASHdigest, &HASHcontext );

	ber_dupbv_x( keys, &digest, ctx );
	keys[1].bv_val = NULL;
	keys[1].bv_len = 0;

	*keysp = keys;

	return LDAP_SUCCESS;
}

static int
octetStringSubstringsMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	int match = 0;
	SubstringsAssertion *sub = assertedValue;
	struct berval left = *value;
	int i;
	ber_len_t inlen = 0;

	/* Add up asserted input length */
	if( sub->sa_initial.bv_val ) {
		inlen += sub->sa_initial.bv_len;
	}
	if( sub->sa_any ) {
		for(i=0; sub->sa_any[i].bv_val != NULL; i++) {
			inlen += sub->sa_any[i].bv_len;
		}
	}
	if( sub->sa_final.bv_val ) {
		inlen += sub->sa_final.bv_len;
	}

	if( sub->sa_initial.bv_val ) {
		if( inlen > left.bv_len ) {
			match = 1;
			goto done;
		}

		match = memcmp( sub->sa_initial.bv_val, left.bv_val,
			sub->sa_initial.bv_len );

		if( match != 0 ) {
			goto done;
		}

		left.bv_val += sub->sa_initial.bv_len;
		left.bv_len -= sub->sa_initial.bv_len;
		inlen -= sub->sa_initial.bv_len;
	}

	if( sub->sa_final.bv_val ) {
		if( inlen > left.bv_len ) {
			match = 1;
			goto done;
		}

		match = memcmp( sub->sa_final.bv_val,
			&left.bv_val[left.bv_len - sub->sa_final.bv_len],
			sub->sa_final.bv_len );

		if( match != 0 ) {
			goto done;
		}

		left.bv_len -= sub->sa_final.bv_len;
		inlen -= sub->sa_final.bv_len;
	}

	if( sub->sa_any ) {
		for(i=0; sub->sa_any[i].bv_val; i++) {
			ber_len_t idx;
			char *p;

retry:
			if( inlen > left.bv_len ) {
				/* not enough length */
				match = 1;
				goto done;
			}

			if( sub->sa_any[i].bv_len == 0 ) {
				continue;
			}

			p = memchr( left.bv_val, *sub->sa_any[i].bv_val, left.bv_len );

			if( p == NULL ) {
				match = 1;
				goto done;
			}

			idx = p - left.bv_val;

			if( idx >= left.bv_len ) {
				/* this shouldn't happen */
				return LDAP_OTHER;
			}

			left.bv_val = p;
			left.bv_len -= idx;

			if( sub->sa_any[i].bv_len > left.bv_len ) {
				/* not enough left */
				match = 1;
				goto done;
			}

			match = memcmp( left.bv_val,
				sub->sa_any[i].bv_val,
				sub->sa_any[i].bv_len );

			if( match != 0 ) {
				left.bv_val++;
				left.bv_len--;
				goto retry;
			}

			left.bv_val += sub->sa_any[i].bv_len;
			left.bv_len -= sub->sa_any[i].bv_len;
			inlen -= sub->sa_any[i].bv_len;
		}
	}

done:
	*matchp = match;
	return LDAP_SUCCESS;
}

/* Substrings Index generation function */
static int
octetStringSubstringsIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	BerVarray values,
	BerVarray *keysp,
	void *ctx )
{
	ber_len_t i, j, nkeys;
	size_t slen, mlen;
	BerVarray keys;

	HASH_CONTEXT HASHcontext;
	unsigned char HASHdigest[HASH_BYTES];
	struct berval digest;
	digest.bv_val = (char *)HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

	nkeys=0;

	for( i=0; values[i].bv_val != NULL; i++ ) {
		/* count number of indices to generate */
		if( flags & SLAP_INDEX_SUBSTR_INITIAL ) {
			if( values[i].bv_len >= SLAP_INDEX_SUBSTR_IF_MAXLEN ) {
				nkeys += SLAP_INDEX_SUBSTR_IF_MAXLEN -
					(SLAP_INDEX_SUBSTR_IF_MINLEN - 1);
			} else if( values[i].bv_len >= SLAP_INDEX_SUBSTR_IF_MINLEN ) {
				nkeys += values[i].bv_len - (SLAP_INDEX_SUBSTR_IF_MINLEN - 1);
			}
		}

		if( flags & SLAP_INDEX_SUBSTR_ANY ) {
			if( values[i].bv_len >= SLAP_INDEX_SUBSTR_ANY_LEN ) {
				nkeys += values[i].bv_len - (SLAP_INDEX_SUBSTR_ANY_LEN - 1);
			}
		}

		if( flags & SLAP_INDEX_SUBSTR_FINAL ) {
			if( values[i].bv_len >= SLAP_INDEX_SUBSTR_IF_MAXLEN ) {
				nkeys += SLAP_INDEX_SUBSTR_IF_MAXLEN -
					( SLAP_INDEX_SUBSTR_IF_MINLEN - 1);
			} else if( values[i].bv_len >= SLAP_INDEX_SUBSTR_IF_MINLEN ) {
				nkeys += values[i].bv_len - (SLAP_INDEX_SUBSTR_IF_MINLEN - 1);
			}
		}
	}

	if( nkeys == 0 ) {
		/* no keys to generate */
		*keysp = NULL;
		return LDAP_SUCCESS;
	}

	keys = slap_sl_malloc( sizeof( struct berval ) * (nkeys+1), ctx );

	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;

	nkeys=0;
	for( i=0; values[i].bv_val != NULL; i++ ) {
		ber_len_t j,max;

		if( ( flags & SLAP_INDEX_SUBSTR_ANY ) &&
			( values[i].bv_len >= SLAP_INDEX_SUBSTR_ANY_LEN ) )
		{
			char pre = SLAP_INDEX_SUBSTR_PREFIX;
			max = values[i].bv_len - (SLAP_INDEX_SUBSTR_ANY_LEN - 1);

			for( j=0; j<max; j++ ) {
				HASH_Init( &HASHcontext );
				if( prefix != NULL && prefix->bv_len > 0 ) {
					HASH_Update( &HASHcontext,
						(unsigned char *)prefix->bv_val, prefix->bv_len );
				}

				HASH_Update( &HASHcontext,
					(unsigned char *)&pre, sizeof( pre ) );
				HASH_Update( &HASHcontext,
					(unsigned char *)syntax->ssyn_oid, slen );
				HASH_Update( &HASHcontext,
					(unsigned char *)mr->smr_oid, mlen );
				HASH_Update( &HASHcontext,
					(unsigned char *)&values[i].bv_val[j],
					SLAP_INDEX_SUBSTR_ANY_LEN );
				HASH_Final( HASHdigest, &HASHcontext );

				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}
		}

		/* skip if too short */ 
		if( values[i].bv_len < SLAP_INDEX_SUBSTR_IF_MINLEN ) continue;

		max = SLAP_INDEX_SUBSTR_IF_MAXLEN < values[i].bv_len
			? SLAP_INDEX_SUBSTR_IF_MAXLEN : values[i].bv_len;

		for( j=SLAP_INDEX_SUBSTR_IF_MINLEN; j<=max; j++ ) {
			char pre;

			if( flags & SLAP_INDEX_SUBSTR_INITIAL ) {
				pre = SLAP_INDEX_SUBSTR_INITIAL_PREFIX;
				HASH_Init( &HASHcontext );
				if( prefix != NULL && prefix->bv_len > 0 ) {
					HASH_Update( &HASHcontext,
						(unsigned char *)prefix->bv_val, prefix->bv_len );
				}
				HASH_Update( &HASHcontext,
					(unsigned char *)&pre, sizeof( pre ) );
				HASH_Update( &HASHcontext,
					(unsigned char *)syntax->ssyn_oid, slen );
				HASH_Update( &HASHcontext,
					(unsigned char *)mr->smr_oid, mlen );
				HASH_Update( &HASHcontext,
					(unsigned char *)values[i].bv_val, j );
				HASH_Final( HASHdigest, &HASHcontext );

				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}

			if( flags & SLAP_INDEX_SUBSTR_FINAL ) {
				pre = SLAP_INDEX_SUBSTR_FINAL_PREFIX;
				HASH_Init( &HASHcontext );
				if( prefix != NULL && prefix->bv_len > 0 ) {
					HASH_Update( &HASHcontext,
						(unsigned char *)prefix->bv_val, prefix->bv_len );
				}
				HASH_Update( &HASHcontext,
					(unsigned char *)&pre, sizeof( pre ) );
				HASH_Update( &HASHcontext,
					(unsigned char *)syntax->ssyn_oid, slen );
				HASH_Update( &HASHcontext,
					(unsigned char *)mr->smr_oid, mlen );
				HASH_Update( &HASHcontext,
					(unsigned char *)&values[i].bv_val[values[i].bv_len-j], j );
				HASH_Final( HASHdigest, &HASHcontext );

				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}

		}
	}

	if( nkeys > 0 ) {
		keys[nkeys].bv_val = NULL;
		*keysp = keys;
	} else {
		ch_free( keys );
		*keysp = NULL;
	}

	return LDAP_SUCCESS;
}

static int
octetStringSubstringsFilter (
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertedValue,
	BerVarray *keysp,
	void *ctx)
{
	SubstringsAssertion *sa;
	char pre;
	ber_len_t nkeys = 0;
	size_t slen, mlen, klen;
	BerVarray keys;
	HASH_CONTEXT HASHcontext;
	unsigned char HASHdigest[HASH_BYTES];
	struct berval *value;
	struct berval digest;

	sa = (SubstringsAssertion *) assertedValue;

	if( flags & SLAP_INDEX_SUBSTR_INITIAL &&
		sa->sa_initial.bv_val != NULL &&
		sa->sa_initial.bv_len >= SLAP_INDEX_SUBSTR_IF_MINLEN )
	{
		nkeys++;
	}

	if( flags & SLAP_INDEX_SUBSTR_ANY && sa->sa_any != NULL ) {
		ber_len_t i;
		for( i=0; sa->sa_any[i].bv_val != NULL; i++ ) {
			if( sa->sa_any[i].bv_len >= SLAP_INDEX_SUBSTR_ANY_LEN ) {
				/* don't bother accounting with stepping */
				nkeys += sa->sa_any[i].bv_len -
					( SLAP_INDEX_SUBSTR_ANY_LEN - 1 );
			}
		}
	}

	if( flags & SLAP_INDEX_SUBSTR_FINAL &&
		sa->sa_final.bv_val != NULL &&
		sa->sa_final.bv_len >= SLAP_INDEX_SUBSTR_IF_MINLEN )
	{
		nkeys++;
	}

	if( nkeys == 0 ) {
		*keysp = NULL;
		return LDAP_SUCCESS;
	}

	digest.bv_val = (char *)HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;

	keys = slap_sl_malloc( sizeof( struct berval ) * (nkeys+1), ctx );
	nkeys = 0;

	if( flags & SLAP_INDEX_SUBSTR_INITIAL &&
		sa->sa_initial.bv_val != NULL &&
		sa->sa_initial.bv_len >= SLAP_INDEX_SUBSTR_IF_MINLEN )
	{
		pre = SLAP_INDEX_SUBSTR_INITIAL_PREFIX;
		value = &sa->sa_initial;

		klen = SLAP_INDEX_SUBSTR_IF_MAXLEN < value->bv_len
			? SLAP_INDEX_SUBSTR_IF_MAXLEN : value->bv_len;

		HASH_Init( &HASHcontext );
		if( prefix != NULL && prefix->bv_len > 0 ) {
			HASH_Update( &HASHcontext,
				(unsigned char *)prefix->bv_val, prefix->bv_len );
		}
		HASH_Update( &HASHcontext,
			(unsigned char *)&pre, sizeof( pre ) );
		HASH_Update( &HASHcontext,
			(unsigned char *)syntax->ssyn_oid, slen );
		HASH_Update( &HASHcontext,
			(unsigned char *)mr->smr_oid, mlen );
		HASH_Update( &HASHcontext,
			(unsigned char *)value->bv_val, klen );
		HASH_Final( HASHdigest, &HASHcontext );

		ber_dupbv_x( &keys[nkeys++], &digest, ctx );
	}

	if( flags & SLAP_INDEX_SUBSTR_ANY && sa->sa_any != NULL ) {
		ber_len_t i, j;
		pre = SLAP_INDEX_SUBSTR_PREFIX;
		klen = SLAP_INDEX_SUBSTR_ANY_LEN;

		for( i=0; sa->sa_any[i].bv_val != NULL; i++ ) {
			if( sa->sa_any[i].bv_len < SLAP_INDEX_SUBSTR_ANY_LEN ) {
				continue;
			}

			value = &sa->sa_any[i];

			for(j=0;
				j <= value->bv_len - SLAP_INDEX_SUBSTR_ANY_LEN;
				j += SLAP_INDEX_SUBSTR_ANY_STEP )
			{
				HASH_Init( &HASHcontext );
				if( prefix != NULL && prefix->bv_len > 0 ) {
					HASH_Update( &HASHcontext,
						(unsigned char *)prefix->bv_val, prefix->bv_len );
				}
				HASH_Update( &HASHcontext,
					(unsigned char *)&pre, sizeof( pre ) );
				HASH_Update( &HASHcontext,
					(unsigned char *)syntax->ssyn_oid, slen );
				HASH_Update( &HASHcontext,
					(unsigned char *)mr->smr_oid, mlen );
				HASH_Update( &HASHcontext,
					(unsigned char *)&value->bv_val[j], klen ); 
				HASH_Final( HASHdigest, &HASHcontext );

				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}
		}
	}

	if( flags & SLAP_INDEX_SUBSTR_FINAL &&
		sa->sa_final.bv_val != NULL &&
		sa->sa_final.bv_len >= SLAP_INDEX_SUBSTR_IF_MINLEN )
	{
		pre = SLAP_INDEX_SUBSTR_FINAL_PREFIX;
		value = &sa->sa_final;

		klen = SLAP_INDEX_SUBSTR_IF_MAXLEN < value->bv_len
			? SLAP_INDEX_SUBSTR_IF_MAXLEN : value->bv_len;

		HASH_Init( &HASHcontext );
		if( prefix != NULL && prefix->bv_len > 0 ) {
			HASH_Update( &HASHcontext,
				(unsigned char *)prefix->bv_val, prefix->bv_len );
		}
		HASH_Update( &HASHcontext,
			(unsigned char *)&pre, sizeof( pre ) );
		HASH_Update( &HASHcontext,
			(unsigned char *)syntax->ssyn_oid, slen );
		HASH_Update( &HASHcontext,
			(unsigned char *)mr->smr_oid, mlen );
		HASH_Update( &HASHcontext,
			(unsigned char *)&value->bv_val[value->bv_len-klen], klen );
		HASH_Final( HASHdigest, &HASHcontext );

		ber_dupbv_x( &keys[nkeys++], &digest, ctx );
	}

	if( nkeys > 0 ) {
		keys[nkeys].bv_val = NULL;
		*keysp = keys;
	} else {
		ch_free( keys );
		*keysp = NULL;
	}

	return LDAP_SUCCESS;
}

static int
bitStringValidate(
	Syntax *syntax,
	struct berval *in )
{
	ber_len_t i;

	/* very unforgiving validation, requires no normalization
	 * before simplistic matching
	 */
	if( in->bv_len < 3 ) {
		return LDAP_INVALID_SYNTAX;
	}

	/*
	 * RFC 2252 section 6.3 Bit String
	 *	bitstring = "'" *binary-digit "'B"
	 *	binary-digit = "0" / "1"
	 * example: '0101111101'B
	 */
	
	if( in->bv_val[0] != '\'' ||
		in->bv_val[in->bv_len-2] != '\'' ||
		in->bv_val[in->bv_len-1] != 'B' )
	{
		return LDAP_INVALID_SYNTAX;
	}

	for( i=in->bv_len-3; i>0; i-- ) {
		if( in->bv_val[i] != '0' && in->bv_val[i] != '1' ) {
			return LDAP_INVALID_SYNTAX;
		}
	}

	return LDAP_SUCCESS;
}

/*
 * Syntax is [RFC2252]:
 *

6.3. Bit String

   ( 1.3.6.1.4.1.1466.115.121.1.6 DESC 'Bit String' )

   Values in this syntax are encoded according to the following BNF:

      bitstring = "'" *binary-digit "'B"

      binary-digit = "0" / "1"

   ... 

6.21. Name And Optional UID

   ( 1.3.6.1.4.1.1466.115.121.1.34 DESC 'Name And Optional UID' )

   Values in this syntax are encoded according to the following BNF:

      NameAndOptionalUID = DistinguishedName [ "#" bitstring ]

   Although the '#' character may occur in a string representation of a
   distinguished name, no additional special quoting is done.  This
   syntax has been added subsequent to RFC 1778.

   Example:

      1.3.6.1.4.1.1466.0=#04024869,O=Test,C=GB#'0101'B

 *
 * draft-ietf-ldapbis-syntaxes-xx.txt says:
 *

3.3.2.  Bit String

   A value of the Bit String syntax is a sequence of binary digits.  The
   LDAP-specific encoding of a value of this syntax is defined by the
   following ABNF:

      BitString    = SQUOTE *binary-digit SQUOTE "B"

      binary-digit = "0" / "1"

   The <SQUOTE> rule is defined in [MODELS].

      Example:
         '0101111101'B

   The LDAP definition for the Bit String syntax is:

      ( 1.3.6.1.4.1.1466.115.121.1.6 DESC 'Bit String' )

   This syntax corresponds to the BIT STRING ASN.1 type from [ASN.1].

   ...

3.3.21.  Name and Optional UID

   A value of the Name and Optional UID syntax is the distinguished name
   [MODELS] of an entity optionally accompanied by a unique identifier
   that serves to differentiate the entity from others with an identical
   distinguished name.

   The LDAP-specific encoding of a value of this syntax is defined by
   the following ABNF:

       NameAndOptionalUID = distinguishedName [ SHARP BitString ]

   The <BitString> rule is defined in Section 3.3.2.  The
   <distinguishedName> rule is defined in [LDAPDN].  The <SHARP> rule is
   defined in [MODELS].

   Note that although the '#' character may occur in the string
   representation of a distinguished name, no additional escaping of
   this character is performed when a <distinguishedName> is encoded in
   a <NameAndOptionalUID>.

      Example:
         1.3.6.1.4.1.1466.0=#04024869,O=Test,C=GB#'0101'B

   The LDAP definition for the Name and Optional UID syntax is:

      ( 1.3.6.1.4.1.1466.115.121.1.34 DESC 'Name And Optional UID' )

   This syntax corresponds to the NameAndOptionalUID ASN.1 type from
   [X.520].

 *
 * draft-ietf-ldapbis-models-xx.txt [MODELS] says:
 *

1.4. Common ABNF Productions

  ...
      SHARP   = %x23 ; octothorpe (or sharp sign) ("#")
  ...
      SQUOTE  = %x27 ; single quote ("'")
  ...
      
 *
 * Note: normalization strips any leading "0"s, unless the
 * bit string is exactly "'0'B", so the normalized example,
 * in slapd, would result in
 * 
 * 1.3.6.1.4.1.1466.0=#04024869,o=test,c=gb#'101'B
 * 
 * Since draft-ietf-ldapbis-dn-xx.txt clarifies that SHARP,
 * i.e. "#", doesn't have to be escaped except when at the
 * beginning of a value, the definition of Name and Optional
 * UID appears to be flawed, because there is no clear means
 * to determine whether the UID part is present or not.
 *
 * Example:
 *
 * 	cn=Someone,dc=example,dc=com#'1'B
 *
 * could be either a NameAndOptionalUID with trailing UID, i.e.
 *
 * 	DN = "cn=Someone,dc=example,dc=com"
 * 	UID = "'1'B"
 * 
 * or a NameAndOptionalUID with no trailing UID, and the AVA
 * in the last RDN made of
 *
 * 	attributeType = dc 
 * 	attributeValue = com#'1'B
 *
 * in fact "com#'1'B" is a valid IA5 string.
 *
 * As a consequence, current slapd code assumes that the
 * presence of portions of a BitString at the end of the string 
 * representation of a NameAndOptionalUID means a BitString
 * is expected, and cause an error otherwise.  This is quite
 * arbitrary, and might change in the future.
 */


static int
nameUIDValidate(
	Syntax *syntax,
	struct berval *in )
{
	int rc;
	struct berval dn, uid;

	if( in->bv_len == 0 ) return LDAP_SUCCESS;

	ber_dupbv( &dn, in );
	if( !dn.bv_val ) return LDAP_OTHER;

	/* if there's a "#", try bitStringValidate()... */
	uid.bv_val = strrchr( dn.bv_val, '#' );
	if ( uid.bv_val ) {
		uid.bv_val++;
		uid.bv_len = dn.bv_len - ( uid.bv_val - dn.bv_val );

		rc = bitStringValidate( NULL, &uid );
		if ( rc == LDAP_SUCCESS ) {
			/* in case of success, trim the UID,
			 * otherwise treat it as part of the DN */
			dn.bv_len -= uid.bv_len + 1;
			uid.bv_val[-1] = '\0';
		}
	}

	rc = dnValidate( NULL, &dn );

	ber_memfree( dn.bv_val );
	return rc;
}

int
nameUIDPretty(
	Syntax *syntax,
	struct berval *val,
	struct berval *out,
	void *ctx )
{
	assert( val );
	assert( out );


	Debug( LDAP_DEBUG_TRACE, ">>> nameUIDPretty: <%s>\n", val->bv_val, 0, 0 );

	if( val->bv_len == 0 ) {
		ber_dupbv_x( out, val, ctx );

	} else if ( val->bv_len > SLAP_LDAPDN_MAXLEN ) {
		return LDAP_INVALID_SYNTAX;

	} else {
		int		rc;
		struct berval	dnval = *val;
		struct berval	uidval = BER_BVNULL;

		uidval.bv_val = strrchr( val->bv_val, '#' );
		if ( uidval.bv_val ) {
			uidval.bv_val++;
			uidval.bv_len = val->bv_len - ( uidval.bv_val - val->bv_val );

			rc = bitStringValidate( NULL, &uidval );

			if ( rc == LDAP_SUCCESS ) {
				ber_dupbv_x( &dnval, val, ctx );
				dnval.bv_len -= uidval.bv_len + 1;
				dnval.bv_val[dnval.bv_len] = '\0';

			} else {
				uidval.bv_val = NULL;
			}
		}

		rc = dnPretty( syntax, &dnval, out, ctx );
		if ( dnval.bv_val != val->bv_val ) {
			slap_sl_free( dnval.bv_val, ctx );
		}
		if( rc != LDAP_SUCCESS ) {
			return rc;
		}

		if( uidval.bv_val ) {
			int	i, c, got1;
			char	*tmp;

			tmp = slap_sl_realloc( out->bv_val, out->bv_len 
				+ STRLENOF( "#" ) + uidval.bv_len + 1,
				ctx );
			if( tmp == NULL ) {
				ber_memfree_x( out->bv_val, ctx );
				return LDAP_OTHER;
			}
			out->bv_val = tmp;
			out->bv_val[out->bv_len++] = '#';
			out->bv_val[out->bv_len++] = '\'';

			got1 = uidval.bv_len < sizeof("'0'B"); 
			for( i = 1; i < uidval.bv_len - 2; i++ ) {
				c = uidval.bv_val[i];
				switch(c) {
					case '0':
						if( got1 ) out->bv_val[out->bv_len++] = c;
						break;
					case '1':
						got1 = 1;
						out->bv_val[out->bv_len++] = c;
						break;
				}
			}

			out->bv_val[out->bv_len++] = '\'';
			out->bv_val[out->bv_len++] = 'B';
			out->bv_val[out->bv_len] = '\0';
		}
	}

	Debug( LDAP_DEBUG_TRACE, "<<< nameUIDPretty: <%s>\n", out->bv_val, 0, 0 );

	return LDAP_SUCCESS;
}

static int
uniqueMemberNormalize(
	slap_mask_t usage,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *val,
	struct berval *normalized,
	void *ctx )
{
	struct berval out;
	int rc;

	assert( SLAP_MR_IS_VALUE_OF_SYNTAX( usage ));

	ber_dupbv_x( &out, val, ctx );
	if ( BER_BVISEMPTY( &out ) ) {
		*normalized = out;

	} else {
		struct berval uid = BER_BVNULL;

		uid.bv_val = strrchr( out.bv_val, '#' );
		if ( uid.bv_val ) {
			uid.bv_val++;
			uid.bv_len = out.bv_len - ( uid.bv_val - out.bv_val );

			rc = bitStringValidate( NULL, &uid );
			if ( rc == LDAP_SUCCESS ) {
				uid.bv_val[-1] = '\0';
				out.bv_len -= uid.bv_len + 1;
			} else {
				uid.bv_val = NULL;
			}
		}

		rc = dnNormalize( 0, NULL, NULL, &out, normalized, ctx );

		if( rc != LDAP_SUCCESS ) {
			slap_sl_free( out.bv_val, ctx );
			return LDAP_INVALID_SYNTAX;
		}

		if( uid.bv_val ) {
			char	*tmp;

			tmp = ch_realloc( normalized->bv_val,
				normalized->bv_len + uid.bv_len
				+ STRLENOF("#") + 1 );
			if ( tmp == NULL ) {
				ber_memfree_x( normalized->bv_val, ctx );
				return LDAP_OTHER;
			}

			normalized->bv_val = tmp;

			/* insert the separator */
			normalized->bv_val[normalized->bv_len++] = '#';

			/* append the UID */
			AC_MEMCPY( &normalized->bv_val[normalized->bv_len],
				uid.bv_val, uid.bv_len );
			normalized->bv_len += uid.bv_len;

			/* terminate */
			normalized->bv_val[normalized->bv_len] = '\0';
		}

		slap_sl_free( out.bv_val, ctx );
	}

	return LDAP_SUCCESS;
}

static int
uniqueMemberMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	int match;
	struct berval *asserted = (struct berval *) assertedValue;
	struct berval assertedDN = *asserted;
	struct berval assertedUID = BER_BVNULL;
	struct berval valueDN = BER_BVNULL;
	struct berval valueUID = BER_BVNULL;

	if ( !BER_BVISEMPTY( asserted ) ) {
		assertedUID.bv_val = strrchr( assertedDN.bv_val, '#' );
		if ( !BER_BVISNULL( &assertedUID ) ) {
			assertedUID.bv_val++;
			assertedUID.bv_len = assertedDN.bv_len
				- ( assertedUID.bv_val - assertedDN.bv_val );

			if ( bitStringValidate( NULL, &assertedUID ) == LDAP_SUCCESS ) {
				assertedDN.bv_len -= assertedUID.bv_len + 1;

			} else {
				BER_BVZERO( &assertedUID );
			}
		}
	}

	if ( !BER_BVISEMPTY( value ) ) {
		valueDN = *value;

		valueUID.bv_val = strrchr( valueDN.bv_val, '#' );
		if ( !BER_BVISNULL( &valueUID ) ) {
			valueUID.bv_val++;
			valueUID.bv_len = valueDN.bv_len
				- ( valueUID.bv_val - valueDN.bv_val );

			if ( bitStringValidate( NULL, &valueUID ) == LDAP_SUCCESS ) {
				valueDN.bv_len -= valueUID.bv_len + 1;

			} else {
				BER_BVZERO( &valueUID );
			}
		}
	}

	if( valueUID.bv_len && assertedUID.bv_len ) {
		match = valueUID.bv_len - assertedUID.bv_len;
		if ( match ) {
			*matchp = match;
			return LDAP_SUCCESS;
		}

		match = memcmp( valueUID.bv_val, assertedUID.bv_val, valueUID.bv_len );
		if( match ) {
			*matchp = match;
			return LDAP_SUCCESS;
		}
	}

	return dnMatch( matchp, flags, syntax, mr, &valueDN, &assertedDN );
}

/*
 * Handling boolean syntax and matching is quite rigid.
 * A more flexible approach would be to allow a variety
 * of strings to be normalized and prettied into TRUE
 * and FALSE.
 */
static int
booleanValidate(
	Syntax *syntax,
	struct berval *in )
{
	/* very unforgiving validation, requires no normalization
	 * before simplistic matching
	 */

	if( in->bv_len == 4 ) {
		if( bvmatch( in, &slap_true_bv ) ) {
			return LDAP_SUCCESS;
		}
	} else if( in->bv_len == 5 ) {
		if( bvmatch( in, &slap_false_bv ) ) {
			return LDAP_SUCCESS;
		}
	}

	return LDAP_INVALID_SYNTAX;
}

static int
booleanMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	/* simplistic matching allowed by rigid validation */
	struct berval *asserted = (struct berval *) assertedValue;
	*matchp = value->bv_len != asserted->bv_len;
	return LDAP_SUCCESS;
}

/*-------------------------------------------------------------------
LDAP/X.500 string syntax / matching rules have a few oddities.  This
comment attempts to detail how slapd(8) treats them.

Summary:
  StringSyntax		X.500	LDAP	Matching/Comments
  DirectoryString	CHOICE	UTF8	i/e + ignore insignificant spaces
  PrintableString	subset	subset	i/e + ignore insignificant spaces
  PrintableString	subset	subset	i/e + ignore insignificant spaces
  NumericString		subset	subset	ignore all spaces
  IA5String			ASCII	ASCII	i/e + ignore insignificant spaces
  TeletexString		T.61	T.61	i/e + ignore insignificant spaces

  TelephoneNumber	subset	subset	i + ignore all spaces and "-"

  See draft-ietf-ldapbis-strpro for details (once published).


Directory String -
  In X.500(93), a directory string can be either a PrintableString,
  a bmpString, or a UniversalString (e.g., UCS (a subset of Unicode)).
  In later versions, more CHOICEs were added.  In all cases the string
  must be non-empty.

  In LDAPv3, a directory string is a UTF-8 encoded UCS string.
  A directory string cannot be zero length.

  For matching, there are both case ignore and exact rules.  Both
  also require that "insignificant" spaces be ignored.
	spaces before the first non-space are ignored;
	spaces after the last non-space are ignored;
	spaces after a space are ignored.
  Note: by these rules (and as clarified in X.520), a string of only
  spaces is to be treated as if held one space, not empty (which
  would be a syntax error).

NumericString
  In ASN.1, numeric string is just a string of digits and spaces
  and could be empty.  However, in X.500, all attribute values of
  numeric string carry a non-empty constraint.  For example: