erl_bits.c

OTP是开放电信平台的简称

/* ``The contents of this file are subject to the Erlang Public License,
 * Version 1.1, (the "License"); you may not use this file except in
 * compliance with the License. You should have received a copy of the
 * Erlang Public License along with this software. If not, it can be
 * retrieved via the world wide web at http://www.erlang.org/.
 * 
 * Software distributed under the License is distributed on an "AS IS"
 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
 * the License for the specific language governing rights and limitations
 * under the License.
 * 
 * The Initial Developer of the Original Code is Ericsson Utvecklings AB.
 * Portions created by Ericsson are Copyright 1999, Ericsson Utvecklings
 * AB. All Rights Reserved.''
 * 
 *     $Id$
 */

#ifdef HAVE_CONFIG_H
#  include "config.h"
#endif

#include "sys.h"
#include "erl_vm.h"
#include "global.h"
#include "erl_process.h"
#include "error.h"
#include "bif.h"
#include "big.h"
#include "erl_bits.h"
#include "erl_binary.h"

#ifdef MAX
#undef MAX
#endif
#define MAX(x,y) (((x)>(y))?(x):(y))
#ifdef MIN
#undef MIN
#endif
#define MIN(x,y) (((x)<(y))?(x):(y))

#if defined(WORDS_BIGENDIAN)
# define BIT_ENDIAN_MACHINE 0
#else
# define BIT_ENDIAN_MACHINE BSF_LITTLE
#endif

#define BIT_IS_MACHINE_ENDIAN(x) (((x)&BSF_LITTLE) == BIT_ENDIAN_MACHINE)

/*
 * MAKE_MASK(n) constructs a mask with n bits.
 * Example: MAKE_MASK(3) returns the binary number 00000111.
 */

#define MAKE_MASK(n) ((1 << (n))-1)

/*
 * MASK_BITS assign src to dst, but preserves the dst bits outside the mask.
 */

#define MASK_BITS(src,dst,mask) (((src) & (mask)) | ((dst) & ~(mask)))

static byte get_bit(byte b, size_t a_offs); 

#if defined(ERTS_SMP)
/* the state resides in the current process' scheduler data */
#elif defined(ERL_BITS_REENTRANT)
/* reentrant API but with a hidden single global state, for testing only */
struct erl_bits_state ErlBitsState_;
#else
/* non-reentrant API with a single global state */
struct erl_bits_state ErlBitsState;
#endif

#define byte_buf	(ErlBitsState.byte_buf_)
#define byte_buf_len	(ErlBitsState.byte_buf_len_)

#ifdef ERTS_SMP
static erts_smp_atomic_t bits_bufs_size;
#endif

Uint
erts_bits_bufs_size(void)
{
#if defined(HEAP_FRAG_ELIM_TEST)
    return 0;
#else
#ifdef ERTS_SMP
    return (Uint) erts_smp_atomic_read(&bits_bufs_size);
#else
    ERL_BITS_DECLARE_STATEP;
    return (Uint) (byte_buf_len + erts_bin_buf_len);
#endif
#endif
}

#if !defined(ERTS_SMP)
static
#endif


void
erts_bits_init_state(ERL_BITS_PROTO_0)
{
    byte_buf_len = 1;
    byte_buf = erts_alloc(ERTS_ALC_T_BITS_BUF, byte_buf_len);

#if !defined(HEAP_FRAG_ELIM_TEST)
    erts_bin_buf_len = 1;
    erts_bin_buf = erts_alloc(ERTS_ALC_T_BITS_BUF, erts_bin_buf_len);
#endif
    erts_bin_offset = 0;
#if defined(ERTS_SMP) && !defined(HEAP_FRAG_ELIM_TEST)
    erts_smp_atomic_add(&bits_bufs_size, byte_buf_len + erts_bin_buf_len);
#endif
}

#if defined(ERTS_SMP)
void
erts_bits_destroy_state(ERL_BITS_PROTO_0)
{
    erts_free(ERTS_ALC_T_BITS_BUF, byte_buf);
#if !defined(HEAP_FRAG_ELIM_TEST)
    erts_free(ERTS_ALC_T_BITS_BUF, erts_bin_buf);
#endif
}
#endif

void
erts_init_bits(void)
{
#if defined(ERTS_SMP)
    erts_smp_atomic_init(&bits_bufs_size, 0);
    /* erl_process.c calls erts_bits_init_state() on all state instances */
#else
    ERL_BITS_DECLARE_STATEP;
    erts_bits_init_state(ERL_BITS_ARGS_0);
#endif
}

#if !defined(HEAP_FRAG_ELIM_TEST)

/****************************************************************
 ***
 *** Matching binaries
 ***
 ****************************************************************/

int
erts_bs_start_match(ERL_BITS_PROTO_1(Eterm Binary))
{
    erts_InitMatchBuf(Binary, return 0);
    return 1;
}

int
erts_bs_skip_bits(ERL_BITS_PROTO_1(Uint num_bits))
{
    Uint new_offset = erts_mb.offset + num_bits;

    if (erts_mb.size < new_offset) {
	return 0;
    } else {
	erts_mb.offset = new_offset;
	return 1;
    }
}

int
erts_bs_skip_bits_all(ERL_BITS_PROTO_0)
{
    erts_mb.offset = erts_mb.size;
    return 1;
}

int
erts_bs_test_tail(ERL_BITS_PROTO_1(Uint num_bits))
{
    return erts_mb.size - erts_mb.offset == num_bits;
}

void
erts_bs_save(ERL_BITS_PROTO_1(int index))
{
    erts_save_mb[index] = erts_mb;
}

void
erts_bs_restore(ERL_BITS_PROTO_1(int index))
{
    erts_mb = erts_save_mb[index];
}

Eterm
erts_bs_get_integer(Process *p, Uint num_bits, unsigned flags)
{
    Uint bytes;
    Uint bits;
    Uint offs;
    byte bigbuf[64];
    byte* LSB;
    byte* MSB;
    Uint* hp;
    Uint v32;
    int sgn = 0;
    Eterm res = THE_NON_VALUE;
    ErlBinMatchBuffer* mb;
    ERL_BITS_DEFINE_STATEP(p);  /* This has to be at the end of the
				   declarations since the macro
				   sometimes expands to nothing.
				   VC++ and old gcc does not like
				   stray ';'s between declarations. */

    mb = &erts_mb;

    if (num_bits == 0) {
	return SMALL_ZERO;
    }

    if (mb->size - mb->offset < num_bits) {	/* Asked for too many bits.  */
	return THE_NON_VALUE;
    }

    bytes = NBYTES(num_bits);
    if ((bits = BIT_OFFSET(num_bits)) == 0) {  /* number of bits in MSB */
	bits = 8;
    }
    offs = 8 - bits;                  /* adjusted offset in MSB */

    if (bytes <= sizeof bigbuf) {
	LSB = bigbuf;
    } else {
	LSB = erts_alloc(ERTS_ALC_T_TMP, bytes);
    }
    MSB = LSB + bytes - 1;

    /*
     * Move bits to temporary buffer. We want the buffer to be stored in
     * little-endian order, since bignums are little-endian.
     */
    
    if (flags & BSF_LITTLE) {
	erts_copy_bits(mb->base, mb->offset, 1, LSB, 0, 1, num_bits);
	*MSB >>= offs;		/* adjust msb */
    } else {
	*MSB = 0;
	erts_copy_bits(mb->base, mb->offset, 1, MSB, offs, -1, num_bits);
    }
    mb->offset += num_bits;

    /*
     * Get the sign bit.
     */
    sgn = 0;
    if ((flags & BSF_SIGNED) && (*MSB & (1<<(bits-1)))) {
	byte* ptr = LSB; 
	byte c = 1;

	/* sign extend MSB */
	*MSB |= ~MAKE_MASK(bits);

	/* two's complement */
	while (ptr <= MSB) {
	    byte pd = ~(*ptr);
	    byte d = pd + c;
	    c = (d < pd);
	    *ptr++ = d;
	}
	sgn = 1;
    }

    /* normalize */
    while ((*MSB == 0) && (MSB > LSB)) {
	MSB--;
	bytes--;
    }

    /* Check for guaranteed small */
    switch (bytes) {
    case 1:
	v32 = LSB[0];
	goto big_small;
    case 2:
	v32 = LSB[0] + (LSB[1]<<8); 
	goto big_small; 
    case 3: 
	v32 = LSB[0] + (LSB[1]<<8) + (LSB[2]<<16); 
	goto big_small;
    case 4:
	v32 = (Uint32)(LSB[0] + (LSB[1]<<8) + (LSB[2]<<16) + (LSB[3]<<24));
#if !defined(ARCH_64)
	if (!IS_USMALL(sgn, v32)) {
	    hp = ArithAlloc(p, BIG_UINT_HEAP_SIZE);
	    if (sgn) {
		hp[0] = make_neg_bignum_header(1);
	    } else {
		hp[0] = make_pos_bignum_header(1);
	    }
	    BIG_DIGIT(hp,0) = DLOW(v32);
	    BIG_DIGIT(hp,1) = DHIGH(v32);
	    res = make_big(hp);
	    break;
	}
#endif
    big_small:
	if (sgn) {
	    res = make_small(-((Sint)v32));
	} else {
	    res = make_small(v32);
	}
	break;
    default:
	hp = ArithAlloc(p, 1+WSIZE(bytes));
	res = bytes_to_big(LSB, bytes, sgn, hp);
#if !defined(ARCH_64)
	ASSERT(is_big(res));
#else
	/* 64 bit CPU: The result may be small. */
	if (is_small(res)) {
	    erts_arith_shrink(p, hp);
	}
#endif
	break;
    }

    if (LSB != bigbuf) {
	erts_free(ERTS_ALC_T_TMP, (void *) LSB);
    }
    return res;
}

Eterm
erts_bs_get_binary(Process *p, Uint num_bits, unsigned flags)
{
    ErlBinMatchBuffer* mb;
    ErlSubBin* sb;
    ERL_BITS_DEFINE_STATEP(p); /* Has to be at the end of declarations */

    mb = &erts_mb;

    if (num_bits == 0) {		/* Empty binary. */
	return new_binary_arith(p, NULL, 0);
    }
    if (mb->size - mb->offset < num_bits) {	/* Asked for too many bits.  */
	return THE_NON_VALUE;
    }

    /*
     * From now on, we can't fail.
     */
    
    sb = (ErlSubBin *) ArithAlloc(p, ERL_SUB_BIN_SIZE);
    sb->thing_word = HEADER_SUB_BIN;
    sb->orig = mb->orig;
    sb->size = BYTE_OFFSET(num_bits);
    sb->bitsize = BIT_OFFSET(num_bits);
    sb->offs = BYTE_OFFSET(mb->offset);
    sb->bitoffs = BIT_OFFSET(mb->offset);
    mb->offset += num_bits;
    return make_binary(sb);
}

Eterm
erts_bs_get_float(Process *p, Uint num_bits, unsigned flags)
{
    Eterm* hp;
    float f32;
    double f64;
    byte* fptr;
    FloatDef f;
    ErlBinMatchBuffer* mb;
    ERL_BITS_DEFINE_STATEP(p); /* Has to be at the end of declarations */

    mb = &erts_mb;

    if (num_bits == 0) {
	f.fd = 0.0;
	hp = ArithAlloc(p, FLOAT_SIZE_OBJECT);
	PUT_DOUBLE(f, hp);
	ArithCheck(p);
	return make_float(hp);
    }
    if (mb->size - mb->offset < num_bits) {	/* Asked for too many bits.  */
	return THE_NON_VALUE;
    }
    if (num_bits == 32) {
	fptr = (byte *) &f32;
    } else if (num_bits == 64) {
	fptr = (byte *) &f64;
    } else {
	return THE_NON_VALUE;
    }

    if (BIT_IS_MACHINE_ENDIAN(flags)) {
	erts_copy_bits(mb->base, mb->offset, 1,
		  fptr, 0, 1,
		  num_bits);
    } else {
	erts_copy_bits(mb->base, mb->offset, 1,
		  fptr + NBYTES(num_bits) - 1, 0, -1,
		  num_bits);
    }
    ERTS_FP_CHECK_INIT(p);
    if (num_bits == 32) {
	ERTS_FP_ERROR_THOROUGH(p, f32, return THE_NON_VALUE);
	f.fd = f32;
    } else {
	ERTS_FP_ERROR_THOROUGH(p, f64, return THE_NON_VALUE);
	f.fd = f64;
    }
    mb->offset += num_bits;
    hp = ArithAlloc(p, FLOAT_SIZE_OBJECT);
    PUT_DOUBLE(f, hp);
    ArithCheck(p);
    return make_float(hp);
}

Eterm
erts_bs_get_binary_all(Process *p)
{
    ErlSubBin* sb;
    Uint size;
    ERL_BITS_DEFINE_STATEP(p);

    size = erts_mb.size-erts_mb.offset;
    if (BIT_OFFSET(size) == 0) {
	sb = (ErlSubBin *) ArithAlloc(p, ERL_SUB_BIN_SIZE);
	sb->thing_word = HEADER_SUB_BIN;
	sb->size = BYTE_OFFSET(size);
	sb->bitsize = BIT_OFFSET(size);
	sb->offs = BYTE_OFFSET(erts_mb.offset);
	sb->bitoffs = BIT_OFFSET(erts_mb.offset);
	sb->orig = erts_mb.orig;
	erts_mb.offset = erts_mb.size;
	return make_binary(sb);
    }
    return THE_NON_VALUE;
}
#endif

/*****************************************************************
 ***
 *** New matching binaries functions
 ***
 *****************************************************************/

#define HeapOnlyAlloc(p, sz)					\
    (ASSERT_EXPR((sz) >= 0),					\
     (ASSERT_EXPR(((HEAP_LIMIT(p) - HEAP_TOP(p)) >= (sz))),	\
      (HEAP_TOP(p) = HEAP_TOP(p) + (sz), HEAP_TOP(p) - (sz))))

#define ReadToVariable(v64, Buffer, x)		\
  do{						\
    int _i;					\
    v64 = 0;					\
    for(_i = 0; _i < x; _i++) {			\
      v64 = ((Uint)Buffer[_i] <<(8*_i)) + v64;	\
	}					\
  }while(0)					\

Eterm
erts_bs_start_match_2(Process *p, Eterm Binary, Uint Max)
{
    if (!is_binary(Binary)) {
	return THE_NON_VALUE;
    } else { 
	Eterm Orig;
	Uint offs;
	Uint* hp;
	Uint NeededSize;
	ErlBinMatchState *ms;
	Uint bitoffs;
	Uint bitsize;
	Uint total_bin_size;
	total_bin_size = binary_size(Binary);
	if ((total_bin_size >> (8*sizeof(Uint)-3)) != 0) {
	    return THE_NON_VALUE;
	}
	NeededSize = ERL_BIN_MATCHSTATE_SIZE(Max);
	hp = HeapOnlyAlloc(p, NeededSize);
	ms = (ErlBinMatchState *) hp;                         
	ERTS_GET_REAL_BIN(Binary, Orig, offs, bitoffs, bitsize);
	ms->thing_word = HEADER_BIN_MATCHSTATE(Max);
	(ms->mb).orig = Orig;
	(ms->mb).base = binary_bytes(Orig);
	(ms->mb).offset = 8 * offs + bitoffs;
	(ms->mb).size = total_bin_size * 8 + (ms->mb).offset + bitsize;
	return make_matchstate(ms);
    }    
}

Eterm
erts_bs_get_integer_2(Process *p, Uint num_bits, unsigned flags, ErlBinMatchBuffer* mb)
{
    Uint bytes;
    Uint bits;
    Uint offs;
    byte bigbuf[64];
    byte* LSB;
    byte* MSB;
    Uint* hp;
    Uint* hp_end;
    Uint words_needed;
    Uint actual;
    Uint v32;
    int sgn = 0;
    Eterm res = THE_NON_VALUE;
	
    if (num_bits == 0) {
	return SMALL_ZERO;
    }
    
    if (mb->size - mb->offset < num_bits) {	/* Asked for too many bits.  */
	return THE_NON_VALUE;
    }

    bytes = NBYTES(num_bits);
    if ((bits = BIT_OFFSET(num_bits)) == 0) {  /* number of bits in MSB */
	bits = 8;
    }
    offs = 8 - bits;                  /* adjusted offset in MSB */

    if (bytes <= sizeof bigbuf) {
	LSB = bigbuf;
    } else {
	LSB = erts_alloc(ERTS_ALC_T_TMP, bytes);
    }
    MSB = LSB + bytes - 1;

    /*
     * Move bits to temporary buffer. We want the buffer to be stored in
     * little-endian order, since bignums are little-endian.
     */
    
    if (flags & BSF_LITTLE) {
	erts_copy_bits(mb->base, mb->offset, 1, LSB, 0, 1, num_bits);
	*MSB >>= offs;		/* adjust msb */
    } else {
	*MSB = 0;
	erts_copy_bits(mb->base, mb->offset, 1, MSB, offs, -1, num_bits);
    }
    mb->offset += num_bits;

    /*
     * Get the sign bit.
     */
    sgn = 0;
    if ((flags & BSF_SIGNED) && (*MSB & (1<<(bits-1)))) {