/src/igraph/src/math/safe_intop.c

Source
/*
   igraph library.
   Copyright (C) 2022 The igraph development team

   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program 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 this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA
*/

#include "math/safe_intop.h"

/* Use IGRAPH_SAFE_ADD() instead unless there is a need to intercept errors. */
igraph_error_t igraph_i_safe_add(igraph_int_t a, igraph_int_t b, igraph_int_t *res) {
    IGRAPH_SAFE_ADD(a, b, res);
    return IGRAPH_SUCCESS;
}

/* Use IGRAPH_SAFE_MULT() instead unless there is a need to intercept errors. */
igraph_error_t igraph_i_safe_mult(igraph_int_t a, igraph_int_t b, igraph_int_t *res) {
    IGRAPH_SAFE_MULT(a, b, res);
    return IGRAPH_SUCCESS;
}

/* Overflow-safe sum of integer vector elements. */
igraph_error_t igraph_i_safe_vector_int_sum(const igraph_vector_int_t *vec, igraph_int_t *res) {
    const igraph_int_t n = igraph_vector_int_size(vec);
    igraph_int_t sum = 0;
    for (igraph_int_t i=0; i < n; ++i) {
        IGRAPH_SAFE_ADD(sum, VECTOR(*vec)[i], &sum);
    }
    *res = sum;
    return IGRAPH_SUCCESS;
}

/* Overflow-safe product of integer vector elements. */
igraph_error_t igraph_i_safe_vector_int_prod(const igraph_vector_int_t *vec, igraph_int_t *res) {
    const igraph_int_t n = igraph_vector_int_size(vec);
    igraph_int_t prod = 1;
    for (igraph_int_t i=0; i < n; ++i) {
        IGRAPH_SAFE_MULT(prod, VECTOR(*vec)[i], &prod);
    }
    *res = prod;
    return IGRAPH_SUCCESS;
}

/**
 *  Rounds up an integer to the next power of 2, with overflow check.
 *  The result for 2, 3 and 4, respectively, would be 2, 4, and 4.
 *  This function must not be called with negative input.
 *  Based on https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
 */
igraph_error_t igraph_i_safe_next_pow_2(igraph_int_t k, igraph_int_t *res) {
    IGRAPH_ASSERT(k >= 0);
    if (k == 0) {
        *res = 0;
        return IGRAPH_SUCCESS;
    }
    k--;
    k |= k >> 1;
    k |= k >> 2;
    k |= k >> 4;
    k |= k >> 8;
    k |= k >> 16;
#if IGRAPH_INTEGER_SIZE == 32
    /* Nothing else to do. */
#elif IGRAPH_INTEGER_SIZE == 64
    k |= k >> 32;
#else
    /* If values other than 32 or 64 become allowed,
     * this code will need to be updated. */
#  error "Unexpected IGRAPH_INTEGER_SIZE value."
#endif
    if (k < IGRAPH_INTEGER_MAX) {
        *res = k+1;
        return IGRAPH_SUCCESS;
    } else {
        IGRAPH_ERRORF("Overflow when computing next power of 2 for %" IGRAPH_PRId ".",
                      IGRAPH_EOVERFLOW, k);
    }
}

/**
 * Computes 2^k as an integer, with overflow check.
 * This function must not be called with negative input.
 */
igraph_error_t igraph_i_safe_exp2(igraph_int_t k, igraph_int_t *res) {
    IGRAPH_ASSERT(k >= 0);
    if (k > IGRAPH_INTEGER_SIZE-2) {
        IGRAPH_ERRORF("Overflow when raising 2 to power %" IGRAPH_PRId ".",
                      IGRAPH_EOVERFLOW, k);
    }
    *res = (igraph_int_t) 1 << k;
    return IGRAPH_SUCCESS;
}

/**
 * Checks if an igraph_real_t with no fractional part is representable as an igraph_int_t.
 * Avoids invoking undefined behaviour.
 * Must not be called with an input that has a non-zero fractional part.
 */
igraph_bool_t igraph_i_is_real_representable_as_integer(igraph_real_t value) {
    /* IGRAPH_INTEGER_MAX is one less than a power of 2, and may not be representable as
     * a floating point number. Thus we cannot safely check that value <= IGRAPH_INTEGER_MAX,
     * as this would convert IGRAPH_INTEGER_MAX to floating point, potentially changing its value.
     * Instead, we compute int_max_plus_1 = IGRAPH_INTEGER_MAX + 1, which is exactly representable
     * since it is a power of 2, and check that value < int_max_plus_1.
     *
     * IGRAPH_INTEGER_MIN is a power of 2 (with negative sign), so there is no such issue.
     *
     * NaNs and infinities are correctly rejected.
     */
    const igraph_real_t int_max_plus_1 = 2.0 * (IGRAPH_INTEGER_MAX / 2 + 1);
    const igraph_real_t int_min = (igraph_real_t) IGRAPH_INTEGER_MIN;
    if (IGRAPH_LIKELY(int_min <= value && value < int_max_plus_1)) {
        return true;
    } else {
        return false;
    }
}

/**
 * Converts an igraph_real_t into an igraph_int_t with range checks to
 * protect from undefined behaviour. The input value is assumed to have no
 * fractional part.
 */
static igraph_error_t igraph_i_safe_real_to_int(igraph_real_t value, igraph_int_t *result) {
    if (igraph_i_is_real_representable_as_integer(value)) {
        *result = (igraph_int_t) value;
        return IGRAPH_SUCCESS;
    } else if (isnan(value)) {
        IGRAPH_ERROR("NaN cannot be converted to an integer.", IGRAPH_EINVAL);
    } else {
        /* %.f ensures exact printing, %g would not */
        IGRAPH_ERRORF("Cannot convert %.f to integer, outside of representable range.", IGRAPH_EOVERFLOW, value);
    }
}

/**
 * Converts an igraph_real_t into an igraph_int_t with range checks to
 * protect from undefined behaviour. The input value is converted into an
 * integer with ceil().
 */
igraph_error_t igraph_i_safe_ceil(igraph_real_t value, igraph_int_t *result) {
    return igraph_i_safe_real_to_int(ceil(value), result);
}

/**
 * Converts an igraph_real_t into an igraph_int_t with range checks to
 * protect from undefined behaviour. The input value is converted into an
 * integer with floor().
 */
igraph_error_t igraph_i_safe_floor(igraph_real_t value, igraph_int_t *result) {
    return igraph_i_safe_real_to_int(floor(value), result);
}

/**
 * Converts an igraph_real_t into an igraph_int_t with range checks to
 * protect from undefined behaviour. The input value is converted into an
 * integer with round().
 *
 * This is typically the slowest of this set of functions.
 */
igraph_error_t igraph_i_safe_round(igraph_real_t value, igraph_int_t* result) {
    return igraph_i_safe_real_to_int(round(value), result);
}

/**
 * Converts an igraph_real_t into an igraph_int_t with range checks to
 * protect from undefined behaviour. The input value is converted into an
 * integer with trunc().
 *
* This is typically the fastest of this set of functions.
 */
igraph_error_t igraph_i_safe_trunc(igraph_real_t value, igraph_int_t* result) {
    return igraph_i_safe_real_to_int(trunc(value), result);
}

Line	Count	Source
1		/*
2		igraph library.
3		Copyright (C) 2022 The igraph development team
4
5		it under the terms of the GNU General Public License as published by
6		the Free Software Foundation; either version 2 of the License, or
7		(at your option) any later version.
8
9		This program is distributed in the hope that it will be useful,
10		but WITHOUT ANY WARRANTY; without even the implied warranty of
11		MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12		GNU General Public License for more details.
13
14		You should have received a copy of the GNU General Public License
15		along with this program; if not, write to the Free Software
16		Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17		02110-1301 USA
18		*/
19
20		#include "math/safe_intop.h"
21
22		/* Use IGRAPH_SAFE_ADD() instead unless there is a need to intercept errors. */
23	0	igraph_error_t igraph_i_safe_add(igraph_int_t a, igraph_int_t b, igraph_int_t *res) {
24	0	IGRAPH_SAFE_ADD(a, b, res);
25	0	return IGRAPH_SUCCESS;
26	0	}
27
28		/* Use IGRAPH_SAFE_MULT() instead unless there is a need to intercept errors. */
29	0	igraph_error_t igraph_i_safe_mult(igraph_int_t a, igraph_int_t b, igraph_int_t *res) {
30	0	IGRAPH_SAFE_MULT(a, b, res);
31	0	return IGRAPH_SUCCESS;
32	0	}
33
34		/* Overflow-safe sum of integer vector elements. */
35	64.2k	igraph_error_t igraph_i_safe_vector_int_sum(const igraph_vector_int_t vec, igraph_int_t res) {
36	64.2k	const igraph_int_t n = igraph_vector_int_size(vec);
37	64.2k	igraph_int_t sum = 0;
38	11.1M	for (igraph_int_t i=0; i < n; ++i) {
39	11.1M	IGRAPH_SAFE_ADD(sum, VECTOR(*vec)[i], &sum);
40	11.1M	}
41	64.2k	*res = sum;
42	64.2k	return IGRAPH_SUCCESS;
43	64.2k	}
44
45		/* Overflow-safe product of integer vector elements. */
46	0	igraph_error_t igraph_i_safe_vector_int_prod(const igraph_vector_int_t vec, igraph_int_t res) {
47	0	const igraph_int_t n = igraph_vector_int_size(vec);
48	0	igraph_int_t prod = 1;
49	0	for (igraph_int_t i=0; i < n; ++i) {
50	0	IGRAPH_SAFE_MULT(prod, VECTOR(*vec)[i], &prod);
51	0	}
52	0	*res = prod;
53	0	return IGRAPH_SUCCESS;
54	0	}
55
56		/**
57		* Rounds up an integer to the next power of 2, with overflow check.
58		* The result for 2, 3 and 4, respectively, would be 2, 4, and 4.
59		* This function must not be called with negative input.
60		* Based on https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
61		*/
62	0	igraph_error_t igraph_i_safe_next_pow_2(igraph_int_t k, igraph_int_t *res) {
63	0	IGRAPH_ASSERT(k >= 0);
64	0	if (k == 0) {
65	0	*res = 0;
66	0	return IGRAPH_SUCCESS;
67	0	}
68	0	k--;
69	0	k \|= k >> 1;
70	0	k \|= k >> 2;
71	0	k \|= k >> 4;
72	0	k \|= k >> 8;
73	0	k \|= k >> 16;
74		#if IGRAPH_INTEGER_SIZE == 32
75		/* Nothing else to do. */
76		#elif IGRAPH_INTEGER_SIZE == 64
77		k \|= k >> 32;
78		#else
79		/* If values other than 32 or 64 become allowed,
80		* this code will need to be updated. */
81		# error "Unexpected IGRAPH_INTEGER_SIZE value."
82		#endif
83	0	if (k < IGRAPH_INTEGER_MAX) {
84	0	*res = k+1;
85	0	return IGRAPH_SUCCESS;
86	0	} else {
87	0	IGRAPH_ERRORF("Overflow when computing next power of 2 for %" IGRAPH_PRId ".",
88	0	IGRAPH_EOVERFLOW, k);
89	0	}
90	0	}
91
92		/**
93		* Computes 2^k as an integer, with overflow check.
94		* This function must not be called with negative input.
95		*/
96	0	igraph_error_t igraph_i_safe_exp2(igraph_int_t k, igraph_int_t *res) {
97	0	IGRAPH_ASSERT(k >= 0);
98	0	if (k > IGRAPH_INTEGER_SIZE-2) {
99	0	IGRAPH_ERRORF("Overflow when raising 2 to power %" IGRAPH_PRId ".",
100	0	IGRAPH_EOVERFLOW, k);
101	0	}
102	0	*res = (igraph_int_t) 1 << k;
103	0	return IGRAPH_SUCCESS;
104	0	}
105
106		/**
107		* Checks if an igraph_real_t with no fractional part is representable as an igraph_int_t.
108		* Avoids invoking undefined behaviour.
109		* Must not be called with an input that has a non-zero fractional part.
110		*/
111	6.49M	igraph_bool_t igraph_i_is_real_representable_as_integer(igraph_real_t value) {
112		/* IGRAPH_INTEGER_MAX is one less than a power of 2, and may not be representable as
113		* a floating point number. Thus we cannot safely check that value <= IGRAPH_INTEGER_MAX,
114		* as this would convert IGRAPH_INTEGER_MAX to floating point, potentially changing its value.
115		* Instead, we compute int_max_plus_1 = IGRAPH_INTEGER_MAX + 1, which is exactly representable
116		* since it is a power of 2, and check that value < int_max_plus_1.
117		*
118		* IGRAPH_INTEGER_MIN is a power of 2 (with negative sign), so there is no such issue.
119		*
120		* NaNs and infinities are correctly rejected.
121		*/
122	6.49M	const igraph_real_t int_max_plus_1 = 2.0 * (IGRAPH_INTEGER_MAX / 2 + 1);
123	6.49M	const igraph_real_t int_min = (igraph_real_t) IGRAPH_INTEGER_MIN;
124	6.49M	if (IGRAPH_LIKELY(int_min <= value && value < int_max_plus_1)) {
125	6.46M	return true;
126	6.46M	} else {
127	30.6k	return false;
128	30.6k	}
129	6.49M	}
130
131		/**
132		* Converts an igraph_real_t into an igraph_int_t with range checks to
133		* protect from undefined behaviour. The input value is assumed to have no
134		* fractional part.
135		*/
136	0	static igraph_error_t igraph_i_safe_real_to_int(igraph_real_t value, igraph_int_t *result) {
137	0	if (igraph_i_is_real_representable_as_integer(value)) {
138	0	*result = (igraph_int_t) value;
139	0	return IGRAPH_SUCCESS;
140	0	} else if (isnan(value)) {
141	0	IGRAPH_ERROR("NaN cannot be converted to an integer.", IGRAPH_EINVAL);
142	0	} else {
143		/* %.f ensures exact printing, %g would not */
144	0	IGRAPH_ERRORF("Cannot convert %.f to integer, outside of representable range.", IGRAPH_EOVERFLOW, value);
145	0	}
146	0	}
147
148		/**
149		* Converts an igraph_real_t into an igraph_int_t with range checks to
150		* protect from undefined behaviour. The input value is converted into an
151		* integer with ceil().
152		*/
153	0	igraph_error_t igraph_i_safe_ceil(igraph_real_t value, igraph_int_t *result) {
154	0	return igraph_i_safe_real_to_int(ceil(value), result);
155	0	}
156
157		/**
158		* Converts an igraph_real_t into an igraph_int_t with range checks to
159		* protect from undefined behaviour. The input value is converted into an
160		* integer with floor().
161		*/
162	0	igraph_error_t igraph_i_safe_floor(igraph_real_t value, igraph_int_t *result) {
163	0	return igraph_i_safe_real_to_int(floor(value), result);
164	0	}
165
166		/**
167		* Converts an igraph_real_t into an igraph_int_t with range checks to
168		* protect from undefined behaviour. The input value is converted into an
169		* integer with round().
170		*
171		* This is typically the slowest of this set of functions.
172		*/
173	0	igraph_error_t igraph_i_safe_round(igraph_real_t value, igraph_int_t* result) {
174	0	return igraph_i_safe_real_to_int(round(value), result);
175	0	}
176
177		/**
178		* Converts an igraph_real_t into an igraph_int_t with range checks to
179		* protect from undefined behaviour. The input value is converted into an
180		* integer with trunc().
181		*
182		* This is typically the fastest of this set of functions.
183		*/
184	0	igraph_error_t igraph_i_safe_trunc(igraph_real_t value, igraph_int_t* result) {
185	0	return igraph_i_safe_real_to_int(trunc(value), result);
186	0	}

Coverage Report

Created: 2026-02-26 07:09