wide-int.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "selftest.h"

Include dependency graph for wide-int.cc:

Macros
#define	HOST_BITS_PER_HALF_WIDE_INT   32
#define	W_TYPE_SIZE   HOST_BITS_PER_WIDE_INT
#define	HALF_INT_MASK   ((HOST_WIDE_INT_1 << HOST_BITS_PER_HALF_WIDE_INT) - 1)
#define	BLOCK_OF(TARGET)
#define	BLOCKS_NEEDED(PREC)
#define	SIGN_MASK(X)

Functions
static unsigned HOST_WIDE_INT	safe_uhwi (const HOST_WIDE_INT *val, unsigned int len, unsigned int i)
static unsigned int	canonize (HOST_WIDE_INT *val, unsigned int len, unsigned int precision)
static unsigned int	canonize_uhwi (HOST_WIDE_INT *val, unsigned int precision)
static HOST_WIDE_INT	selt (const HOST_WIDE_INT *a, unsigned int len, unsigned int blocks_needed, unsigned int small_prec, unsigned int index, signop sgn)
static HOST_WIDE_INT	top_bit_of (const HOST_WIDE_INT *a, unsigned int len, unsigned int prec)
static void	wi_unpack (unsigned HOST_HALF_WIDE_INT *result, const HOST_WIDE_INT *input, unsigned int in_len, unsigned int out_len, unsigned int prec, signop sgn)
static unsigned int	wi_pack (HOST_WIDE_INT *result, const unsigned HOST_HALF_WIDE_INT *input, unsigned int in_len, unsigned int precision)
static int	divmod_internal_2 (unsigned HOST_HALF_WIDE_INT *b_quotient, unsigned HOST_HALF_WIDE_INT *b_remainder, unsigned HOST_HALF_WIDE_INT *b_dividend, unsigned HOST_HALF_WIDE_INT *b_divisor, int m, int n)
static void	rshift_large_common (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, unsigned int xlen, unsigned int shift, unsigned int len)
void	gt_ggc_mx (widest_int *)
void	gt_pch_nx (widest_int *, void(*)(void *, void *), void *)
void	gt_pch_nx (widest_int *)
DEBUG_FUNCTION void	debug (const wide_int &ref)
DEBUG_FUNCTION void	debug (const wide_int *ptr)
DEBUG_FUNCTION void	debug (const widest_int &ref)
DEBUG_FUNCTION void	debug (const widest_int *ptr)

Variables
static const HOST_WIDE_INT	zeros [1] = {}

Macro Definition Documentation

BLOCK_OF

#define BLOCK_OF

(

TARGET

)

Value:

((TARGET) / HOST_BITS_PER_WIDE_INT)

BLOCKS_NEEDED

#define BLOCKS_NEEDED

(

PREC

)

Value:

(PREC ? CEIL (PREC, HOST_BITS_PER_WIDE_INT) : 1)

Referenced by wi::arshift_large(), wi::bswap_large(), canonize(), wi::cmps_large(), wi::cmpu_large(), wi::divmod_internal(), wi::force_to_size(), wi::from_buffer(), wi::lrshift_large(), wi::lshift_large(), wi::lts_p_large(), wi::ltu_p_large(), wi::mul_internal(), wi_pack(), and wi_unpack().

HALF_INT_MASK

#define HALF_INT_MASK   ((HOST_WIDE_INT_1 << HOST_BITS_PER_HALF_WIDE_INT) - 1)

Quantities to deal with values that hold half of a wide int.  Used
in multiply and divide.   

Referenced by divmod_internal_2(), wi::mul_internal(), and wi_unpack().

HOST_BITS_PER_HALF_WIDE_INT

#define HOST_BITS_PER_HALF_WIDE_INT   32

Operations with very long integers.
   Copyright (C) 2012-2025 Free Software Foundation, Inc.
   Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3, or (at your option) any
later version.

GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.   

Referenced by wi::divmod_internal(), divmod_internal_2(), wi::mul_internal(), wi_pack(), and wi_unpack().

SIGN_MASK

#define SIGN_MASK

(

X

)

Value:

((HOST_WIDE_INT) (X) < 0 ? -1 : 0)

Referenced by canonize(), wi::mul_internal(), and selt().

W_TYPE_SIZE

#define W_TYPE_SIZE   HOST_BITS_PER_WIDE_INT

Function Documentation

canonize()

static unsigned int canonize ( HOST_WIDE_INT * val, unsigned int len, unsigned int precision )

static

Convert the integer in VAL to canonical form, returning its new length.
LEN is the number of blocks currently in VAL and PRECISION is the number
of bits in the integer it represents.

This function only changes the representation, not the value.   

References BLOCKS_NEEDED, HOST_BITS_PER_WIDE_INT, HOST_WIDE_INT_M1, i, sext_hwi(), and SIGN_MASK.

Referenced by wi::add_large(), wi::and_large(), wi::and_not_large(), wi::arshift_large(), wi::bitreverse_large(), wi::bswap_large(), wi::force_to_size(), wi::from_array(), wi::from_buffer(), wi::from_mpz(), wi::lrshift_large(), wi::lshift_large(), wi::or_large(), wi::or_not_large(), wi::set_bit_large(), wi::sext_large(), wi::sub_large(), wi_pack(), wi::xor_large(), and wi::zext_large().

canonize_uhwi()

static unsigned int canonize_uhwi ( HOST_WIDE_INT * val, unsigned int precision )

inlinestatic

VAL[0] is the unsigned result of an operation.  Canonize it by adding
another 0 block if needed, and return number of blocks needed.   

References HOST_BITS_PER_WIDE_INT.

Referenced by wi::divmod_internal().

debug() [1/4]

DEBUG_FUNCTION void debug

(

const wide_int &

ref

)

We could add all the above ::dump variants here, but wide_int and
widest_int should handle the common cases.  Besides, you can always
call the dump method directly.   

References generic_wide_int< storage >::dump().

debug() [2/4]

DEBUG_FUNCTION void debug

(

const wide_int *

ptr

)

References debug.

debug() [3/4]

DEBUG_FUNCTION void debug

(

const widest_int &

ref

)

References generic_wide_int< storage >::dump().

debug() [4/4]

DEBUG_FUNCTION void debug

(

const widest_int *

ptr

)

References debug.

divmod_internal_2()

static int divmod_internal_2 ( unsigned HOST_HALF_WIDE_INT * b_quotient, unsigned HOST_HALF_WIDE_INT * b_remainder, unsigned HOST_HALF_WIDE_INT * b_dividend, unsigned HOST_HALF_WIDE_INT * b_divisor, int m, int n )

static

Compute B_QUOTIENT and B_REMAINDER from B_DIVIDEND/B_DIVISOR.  The
algorithm is a small modification of the algorithm in Hacker's
Delight by Warren, which itself is a small modification of Knuth's
algorithm.  M is the number of significant elements of U however
there needs to be at least one extra element of B_DIVIDEND
allocated, N is the number of elements of B_DIVISOR.
Return new value for N.   

References b, clz_hwi(), HALF_INT_MASK, HOST_BITS_PER_HALF_WIDE_INT, HOST_WIDE_INT_1U, i, and MIN.

Referenced by wi::divmod_internal().

gt_ggc_mx()

void gt_ggc_mx

(

widest_int *

)

gt_pch_nx() [1/2]

void gt_pch_nx

(

widest_int *

)

gt_pch_nx() [2/2]

void gt_pch_nx	(	widest_int *	,
		void(*	)(void *, void *),
		void *	)

rshift_large_common()

static void rshift_large_common ( HOST_WIDE_INT * val, const HOST_WIDE_INT * xval, unsigned int xlen, unsigned int shift, unsigned int len )

static

Right shift XVAL by SHIFT and store the result in VAL.  LEN is the
number of blocks in VAL.  The input has XPRECISION bits and the
output has XPRECISION - SHIFT bits.   

References HOST_BITS_PER_WIDE_INT, i, safe_uhwi(), and shift.

Referenced by wi::arshift_large(), and wi::lrshift_large().

safe_uhwi()

static unsigned HOST_WIDE_INT safe_uhwi ( const HOST_WIDE_INT * val, unsigned int len, unsigned int i )

static

Return the value a VAL[I] if I < LEN, otherwise, return 0 or -1
based on the top existing bit of VAL.  

References HOST_WIDE_INT_M1, and i.

Referenced by wi::bitreverse_large(), wi::bswap_large(), wi::lshift_large(), rshift_large_common(), wi::set_bit_large(), and wi_unpack().

selt()

static HOST_WIDE_INT selt ( const HOST_WIDE_INT * a, unsigned int len, unsigned int blocks_needed, unsigned int small_prec, unsigned int index, signop sgn )

inlinestatic

This function hides the fact that we cannot rely on the bits beyond
the precision.  This issue comes up in the relational comparisions
where we do allow comparisons of values of different precisions.   

References a, sext_hwi(), SIGN_MASK, SIGNED, and zext_hwi().

Referenced by wi::cmps_large(), wi::cmpu_large(), wi::lts_p_large(), and wi::ltu_p_large().

top_bit_of()

static HOST_WIDE_INT top_bit_of ( const HOST_WIDE_INT * a, unsigned int len, unsigned int prec )

inlinestatic

Find the highest bit represented in a wide int.  This will in
general have the same value as the sign bit.   

References a, and HOST_BITS_PER_WIDE_INT.

Referenced by wi::add_large(), wi::and_large(), wi::and_not_large(), wi::or_large(), wi::or_not_large(), wi::sub_large(), wi_unpack(), and wi::xor_large().

wi_pack()

static unsigned int wi_pack ( HOST_WIDE_INT * result, const unsigned HOST_HALF_WIDE_INT * input, unsigned int in_len, unsigned int precision )

static

The inverse of wi_unpack.  IN_LEN is the number of input
blocks and PRECISION is the precision of the result.  Return the
number of blocks in the canonicalized result.   

References BLOCKS_NEEDED, canonize(), HOST_BITS_PER_HALF_WIDE_INT, and i.

Referenced by wi::divmod_internal(), and wi::mul_internal().

wi_unpack()

static void wi_unpack ( unsigned HOST_HALF_WIDE_INT * result, const HOST_WIDE_INT * input, unsigned int in_len, unsigned int out_len, unsigned int prec, signop sgn )

static

Subroutines of the multiplication and division operations.  Unpack
the first IN_LEN HOST_WIDE_INTs in INPUT into 2 * IN_LEN
HOST_HALF_WIDE_INTs of RESULT.  The rest of RESULT is filled by
uncompressing the top bit of INPUT[IN_LEN - 1].   

References BLOCKS_NEEDED, HALF_INT_MASK, HOST_BITS_PER_HALF_WIDE_INT, HOST_BITS_PER_WIDE_INT, i, safe_uhwi(), sext_hwi(), SIGNED, top_bit_of(), and zext_hwi().

Referenced by wi::divmod_internal(), and wi::mul_internal().

Variable Documentation

zeros

const HOST_WIDE_INT zeros[1] = {}

static

Do not include longlong.h when compiler is clang-based. See PR61146.   

Referenced by adjust_equivalence_range(), and wi::divmod_internal().