1# 2# Copyright (C) 2017 The Android Open Source Project 3# 4# Licensed under the Apache License, Version 2.0 (the "License"); 5# you may not use this file except in compliance with the License. 6# You may obtain a copy of the License at 7# 8# http://www.apache.org/licenses/LICENSE-2.0 9# 10# Unless required by applicable law or agreed to in writing, software 11# distributed under the License is distributed on an "AS IS" BASIS, 12# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13# See the License for the specific language governing permissions and 14# limitations under the License. 15# 16 17########################################################### 18# Basic math functions for non-negative integers <= 100 19# 20# (SDK versions for example) 21########################################################### 22__MATH_POS_NUMBERS := 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 \ 23 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 \ 24 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 \ 25 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 \ 26 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 27__MATH_NUMBERS := 0 $(__MATH_POS_NUMBERS) 28__MATH_ONE_NUMBERS := 0 1 2 3 4 5 6 7 8 9 29 30math-error = $(call pretty-error,$(1)) 31math-expect := 32math-expect-true := 33math-expect := 34math-expect-error := 35 36# Run the math tests with: 37# make -f ${ANDROID_BUILD_TOP}/build/make/common/math.mk RUN_MATH_TESTS=true 38# $(get_build_var CKATI) -f ${ANDROID_BUILD_TOP}//build/make/common/math.mk RUN_MATH_TESTS=true 39ifdef RUN_MATH_TESTS 40 ifndef empty 41 empty := 42 space := $(empty) $(empty) 43 endif 44 MATH_TEST_FAILURE := 45 MATH_TEST_ERROR := 46 math-error = $(if $(MATH_TEST_ERROR),,$(eval MATH_TEST_ERROR:=$(1))) 47 define math-expect 48 $(eval got:=$$$1) \ 49 $(if $(subst $(got),,$(2))$(subst $(2),,$(got))$(MATH_TEST_ERROR), \ 50 $(if $(MATH_TEST_ERROR),$(warning $(MATH_TEST_ERROR)),$(warning $$$1 '$(got)' != '$(2)')) \ 51 $(eval MATH_TEST_FAILURE := true)) \ 52 $(eval MATH_TEST_ERROR :=) \ 53 $(eval got:=) 54 endef 55 math-expect-true = $(call math-expect,$(1),true) 56 math-expect-false = $(call math-expect,$(1),) 57 58 define math-expect-error 59 $(eval got:=$$$1) \ 60 $(if $(subst $(MATH_TEST_ERROR),,$(2))$(subst $(2),,$(MATH_TEST_ERROR)), \ 61 $(warning '$(MATH_TEST_ERROR)' != '$(2)') \ 62 $(eval MATH_TEST_FAILURE := true)) \ 63 $(eval MATH_TEST_ERROR :=) \ 64 $(eval got:=) 65 endef 66endif 67 68# Returns true if $(1) is a non-negative integer <= 100, otherwise returns nothing. 69define math_is_number_in_100 70$(strip \ 71 $(if $(1),,$(call math-error,Argument missing)) \ 72 $(if $(word 2,$(1)),$(call math-error,Multiple words in a single argument: $(1))) \ 73 $(if $(filter $(1),$(__MATH_NUMBERS)),true)) 74endef 75 76# Same with math_is_number_in_100, but no limit. 77define _math_ext_is_number 78$(strip \ 79 $(if $(1),,$(call math-error,Argument missing)) \ 80 $(if $(word 2,$(1)),$(call math-error,Multiple words in a single argument: $(1))) \ 81 $(eval should_empty:=$(1)) \ 82 $(foreach num,$(__MATH_ONE_NUMBERS),\ 83 $(eval should_empty:=$(subst $(num),$(empty),$(should_empty)))) \ 84 $(if $(should_empty),,true)) 85endef 86 87# Returns true if $(1) is a non-negative integer. 88define math_is_number 89$(strip $(if $(call math_is_number_in_100,$(1)),true,$(call _math_ext_is_number,$(1)))) 90endef 91 92# Returns true if $(1) is a positive or negative integer. 93define math_is_int 94$(call math_is_number,$(patsubst -%,%,$(1))) 95endef 96 97define math_is_zero 98$(strip \ 99 $(if $(word 2,$(1)),$(call math-error,Multiple words in a single argument: $(1))) \ 100 $(if $(filter 0,$(1)),true)) 101endef 102 103$(call math-expect-true,(call math_is_number,0)) 104$(call math-expect-true,(call math_is_number,2)) 105$(call math-expect-true,(call math_is_number,202412)) 106$(call math-expect-false,(call math_is_number,foo)) 107$(call math-expect-false,(call math_is_number,-1)) 108$(call math-expect-true,(call math_is_int,50)) 109$(call math-expect-true,(call math_is_int,-1)) 110$(call math-expect-true,(call math_is_int,-528)) 111$(call math-expect-true,(call math_is_int,-0)) 112$(call math-expect-false,(call math_is_int,--1)) 113$(call math-expect-false,(call math_is_int,-)) 114$(call math-expect-error,(call math_is_number,1 2),Multiple words in a single argument: 1 2) 115$(call math-expect-error,(call math_is_number,no 2),Multiple words in a single argument: no 2) 116 117$(call math-expect-true,(call math_is_zero,0)) 118$(call math-expect-false,(call math_is_zero,1)) 119$(call math-expect-false,(call math_is_zero,foo)) 120$(call math-expect-error,(call math_is_zero,1 2),Multiple words in a single argument: 1 2) 121$(call math-expect-error,(call math_is_zero,no 2),Multiple words in a single argument: no 2) 122 123define _math_check_valid 124$(if $(call math_is_number_in_100,$(1)),,$(call math-error,Only non-negative integers <= 100 are supported (not $(1)))) 125endef 126 127$(call math-expect,(call _math_check_valid,0)) 128$(call math-expect,(call _math_check_valid,1)) 129$(call math-expect,(call _math_check_valid,100)) 130$(call math-expect-error,(call _math_check_valid,-1),Only non-negative integers <= 100 are supported (not -1)) 131$(call math-expect-error,(call _math_check_valid,101),Only non-negative integers <= 100 are supported (not 101)) 132$(call math-expect-error,(call _math_check_valid,),Argument missing) 133$(call math-expect-error,(call _math_check_valid,1 2),Multiple words in a single argument: 1 2) 134 135# return a list containing integers ranging from [$(1),$(2)] 136define int_range_list 137$(strip \ 138 $(call _math_check_valid,$(1))$(call _math_check_valid,$(2)) \ 139 $(if $(call math_is_zero,$(1)),0)\ 140 $(wordlist $(if $(call math_is_zero,$(1)),1,$(1)),$(2),$(__MATH_POS_NUMBERS))) 141endef 142 143$(call math-expect,(call int_range_list,0,1),0 1) 144$(call math-expect,(call int_range_list,1,1),1) 145$(call math-expect,(call int_range_list,1,2),1 2) 146$(call math-expect,(call int_range_list,2,1),) 147$(call math-expect-error,(call int_range_list,1,101),Only non-negative integers <= 100 are supported (not 101)) 148 149# Split an integer into a list of digits 150define _math_number_to_list 151$(strip \ 152 $(if $(call _math_ext_is_number,$(1)),,\ 153 $(call math-error,Only non-negative integers are supported (not $(1)))) \ 154 $(eval num_list:=$(1)) \ 155 $(foreach num,$(__MATH_ONE_NUMBERS),\ 156 $(eval num_list:=$(subst $(num),$(space)$(num),$(num_list)))) \ 157 $(if $(filter $(words $(num_list)),$(__MATH_ONE_NUMBERS)),,\ 158 $(call math-error,Only non-negative integers with less than 9 digits are supported (not $(1)))) \ 159 $(if $(filter 0,$(word 1,$(num_list))),\ 160 $(call math-error,Only non-negative integers without leading zeros are supported (not $(1)))) \ 161 $(num_list)) 162endef 163 164$(call math-expect,(call _math_number_to_list,123),1 2 3) 165$(call math-expect-error,(call _math_number_to_list,123 456),Multiple words in a single argument: 123 456) 166$(call math-expect-error,(call _math_number_to_list,-123),Only non-negative integers are supported (not -123)) 167$(call math-expect-error,(call _math_number_to_list,002),Only non-negative integers without leading zeros are supported (not 002)) 168$(call math-expect-error,(call _math_number_to_list,1234567890),Only non-negative integers with less than 9 digits are supported (not 1234567890)) 169 170# Compare 1-digit integer $(1) and $(2). 171# Returns 1 if $(1) > $(2), -1 if $(1) < $(2), nothing if equals. 172define _math_1digit_comp 173$(strip \ 174 $(if $(filter $(1),$(2)),,\ 175 $(if $(filter $(1),$(firstword $(filter $(1) $(2),$(__MATH_ONE_NUMBERS)))),-1,1))) 176endef 177 178$(call math-expect,(call _math_1digit_comp,1,1)) 179$(call math-expect,(call _math_1digit_comp,0,9),-1) 180$(call math-expect,(call _math_1digit_comp,3,1),1) 181 182# Compare the same $(3)-digit-length integers $(1) and $(2) that are split into a list of digits. 183# Returns 1 if $(1) > $(2), -1 if $(1) < $(2), nothing if equals. 184define _math_list_comp 185$(strip \ 186 $(eval ans:=) \ 187 $(foreach num,$(call int_range_list,1,$(3)),\ 188 $(if $(ans),,$(eval ans:=$(call _math_1digit_comp,$(word $(num),$(1)),$(word $(num),$(2)))))) \ 189 $(ans)) 190endef 191 192# Compare any two non-negative integers $(1) and $(2). 193# Returns 1 if $(1) > $(2), -1 if $(1) < $(2), nothing if equals. 194define _math_ext_comp 195$(strip \ 196 $(eval num_list1:=$(call _math_number_to_list,$(1))) \ 197 $(eval len1:=$(words $(num_list1))) \ 198 $(eval num_list2:=$(call _math_number_to_list,$(2))) \ 199 $(eval len2:=$(words $(num_list2))) \ 200 $(eval comp:=$(call _math_1digit_comp,$(len1),$(len2))) \ 201 $(if $(comp),$(comp),$(call _math_list_comp,$(num_list1),$(num_list2),$(len1)))) 202endef 203 204$(call math-expect,(call _math_ext_comp,5,10),-1) 205$(call math-expect,(call _math_ext_comp,12345,12345)) 206$(call math-expect,(call _math_ext_comp,500,5),1) 207$(call math-expect,(call _math_ext_comp,202404,202504),-1) 208 209# Returns the greater of $1 or $2. 210# If $1 or $2 is not a positive integer, then an error is generated. 211define math_max 212$(strip \ 213 $(if $(filter truetrue,$(call math_is_number_in_100,$(1))$(call math_is_number_in_100,$(2))),\ 214 $(lastword $(filter $(1) $(2),$(__MATH_NUMBERS))),\ 215 $(if $(filter 1,$(call _math_ext_comp,$(1),$(2))),$(1),$(2)))) 216endef 217 218# Returns the lesser of $1 or $2. 219define math_min 220$(strip \ 221 $(if $(filter truetrue,$(call math_is_number_in_100,$(1))$(call math_is_number_in_100,$(2))),\ 222 $(firstword $(filter $(1) $(2),$(__MATH_NUMBERS))),\ 223 $(if $(filter -1,$(call _math_ext_comp,$(1),$(2))),$(1),$(2)))) 224endef 225 226$(call math-expect-error,(call math_max),Argument missing) 227$(call math-expect-error,(call math_max,1),Argument missing) 228$(call math-expect-error,(call math_max,1 2,3),Multiple words in a single argument: 1 2) 229$(call math-expect-error,(call math_min,1,2 3),Multiple words in a single argument: 2 3) 230$(call math-expect,(call math_max,0,1),1) 231$(call math-expect,(call math_max,1,0),1) 232$(call math-expect,(call math_max,1,1),1) 233$(call math-expect,(call math_max,5,42),42) 234$(call math-expect,(call math_max,42,5),42) 235$(call math-expect,(call math_min,0,1),0) 236$(call math-expect,(call math_min,1,0),0) 237$(call math-expect,(call math_min,1,1),1) 238$(call math-expect,(call math_min,7,32),7) 239$(call math-expect,(call math_min,32,7),7) 240 241$(call math-expect,(call math_max,32759,7),32759) 242$(call math-expect,(call math_max,7,32759),32759) 243$(call math-expect,(call math_max,202404,202505),202505) 244$(call math-expect,(call math_max,202404,202404),202404) 245$(call math-expect,(call math_min,8908527,32),32) 246$(call math-expect,(call math_min,32,8908527),32) 247$(call math-expect,(call math_min,202404,202505),202404) 248$(call math-expect,(call math_min,202404,202404),202404) 249 250define math_gt_or_eq 251$(if $(filter $(1),$(call math_max,$(1),$(2))),true) 252endef 253 254define math_gt 255$(if $(call math_gt_or_eq,$(2),$(1)),,true) 256endef 257 258define math_lt_or_eq 259$(if $(call math_gt_or_eq,$(2),$(1)),true) 260endef 261 262define math_lt 263$(if $(call math_gt_or_eq,$(1),$(2)),,true) 264endef 265 266$(call math-expect-true,(call math_gt_or_eq, 2, 1)) 267$(call math-expect-true,(call math_gt_or_eq, 1, 1)) 268$(call math-expect-false,(call math_gt_or_eq, 1, 2)) 269$(call math-expect-true,(call math_gt, 4, 3)) 270$(call math-expect-false,(call math_gt, 5, 5)) 271$(call math-expect-false,(call math_gt, 6, 7)) 272$(call math-expect-true,(call math_lt_or_eq, 11, 11)) 273$(call math-expect-false,(call math_lt_or_eq, 25, 15)) 274$(call math-expect-true,(call math_lt_or_eq, 9, 16)) 275$(call math-expect-false,(call math_lt, 1, 0)) 276$(call math-expect-false,(call math_lt, 8, 8)) 277$(call math-expect-true,(call math_lt, 10, 11)) 278 279$(call math-expect-true,(call math_gt_or_eq, 2573904, 2573900)) 280$(call math-expect-true,(call math_gt_or_eq, 12345, 12345)) 281$(call math-expect-false,(call math_gt_or_eq, 56, 2780)) 282 283# $1 is the variable name to increment 284define inc_and_print 285$(strip $(eval $(1) := $($(1)) .)$(words $($(1)))) 286endef 287 288ifdef RUN_MATH_TESTS 289a := 290$(call math-expect,(call inc_and_print,a),1) 291$(call math-expect,(call inc_and_print,a),2) 292$(call math-expect,(call inc_and_print,a),3) 293$(call math-expect,(call inc_and_print,a),4) 294endif 295 296# Returns the words in $2 that are numbers and are less than $1 297define numbers_less_than 298$(strip \ 299 $(foreach n,$2, \ 300 $(if $(call math_is_number,$(n)), \ 301 $(if $(call math_lt,$(n),$(1)), \ 302 $(n))))) 303endef 304 305$(call math-expect,(call numbers_less_than,0,0 1 2 3),) 306$(call math-expect,(call numbers_less_than,1,0 2 1 3),0) 307$(call math-expect,(call numbers_less_than,2,0 2 1 3),0 1) 308$(call math-expect,(call numbers_less_than,3,0 2 1 3),0 2 1) 309$(call math-expect,(call numbers_less_than,4,0 2 1 3),0 2 1 3) 310$(call math-expect,(call numbers_less_than,3,0 2 1 3 2),0 2 1 2) 311$(call math-expect,(call numbers_less_than,100,0 1000 50 101 100),0 50) 312 313# Returns the words in $2 that are numbers and are greater or equal to $1 314define numbers_greater_or_equal_to 315$(strip \ 316 $(foreach n,$2, \ 317 $(if $(call math_is_number,$(n)), \ 318 $(if $(call math_gt_or_eq,$(n),$(1)), \ 319 $(n))))) 320endef 321 322$(call math-expect,(call numbers_greater_or_equal_to,4,0 1 2 3),) 323$(call math-expect,(call numbers_greater_or_equal_to,3,0 2 1 3),3) 324$(call math-expect,(call numbers_greater_or_equal_to,2,0 2 1 3),2 3) 325$(call math-expect,(call numbers_greater_or_equal_to,1,0 2 1 3),2 1 3) 326$(call math-expect,(call numbers_greater_or_equal_to,0,0 2 1 3),0 2 1 3) 327$(call math-expect,(call numbers_greater_or_equal_to,1,0 2 1 3 2),2 1 3 2) 328 329# 10,001 = 10 ** 4 + 1, contains 10,001 x's, so 1 more than 10,000 (future) API level 330_INT_LIMIT_WORDS := x $(foreach a,0 1 2 3 4 5 6 7 8 9,$(foreach b,0 1 2 3 4 5 6 7 8 9,\ 331 $(foreach c,0 1 2 3 4 5 6 7 8 9,x x x x x x x x x x))) 332 333define _int_encode 334$(if $(filter $(words x $(_INT_LIMIT_WORDS)),$(words $(wordlist 1,$(1),x $(_INT_LIMIT_WORDS)))),\ 335 $(call math-error,integer greater than $(words $(_INT_LIMIT_WORDS)) is not supported!),\ 336 $(wordlist 1,$(1),$(_INT_LIMIT_WORDS))) 337endef 338 339# _int_max returns the maximum of the two arguments 340# input: two (x) lists; output: one (x) list 341# integer cannot be passed in directly. It has to be converted using _int_encode. 342define _int_max 343$(subst xx,x,$(join $(1),$(2))) 344endef 345 346# first argument is greater than second argument 347# output: non-empty if true 348# integer cannot be passed in directly. It has to be converted using _int_encode. 349define _int_greater-than 350$(filter-out $(words $(2)),$(words $(call _int_max,$(1),$(2)))) 351endef 352 353# first argument equals to second argument 354# output: non-empty if true 355# integer cannot be passed in directly. It has to be converted using _int_encode. 356define _int_equal 357$(filter $(words $(1)),$(words $(2))) 358endef 359 360# first argument is greater than or equal to second argument 361# output: non-empty if true 362# integer cannot be passed in directly. It has to be converted using _int_encode. 363define _int_greater-or-equal 364$(call _int_greater-than,$(1),$(2))$(call _int_equal,$(1),$(2)) 365endef 366 367define int_plus 368$(words $(call _int_encode,$(1)) $(call _int_encode,$(2))) 369endef 370 371$(call math-expect,(call int_plus,0,0),0) 372$(call math-expect,(call int_plus,0,1),1) 373$(call math-expect,(call int_plus,1,0),1) 374$(call math-expect,(call int_plus,1,100),101) 375$(call math-expect,(call int_plus,100,100),200) 376 377define int_subtract 378$(strip \ 379 $(if $(call _int_greater-or-equal,$(call _int_encode,$(1)),$(call _int_encode,$(2))),\ 380 $(words $(filter-out xx,$(join $(call _int_encode,$(1)),$(call _int_encode,$(2))))),\ 381 $(call math-error,subtract underflow $(1) - $(2)))) 382endef 383 384$(call math-expect,(call int_subtract,0,0),0) 385$(call math-expect,(call int_subtract,1,0),1) 386$(call math-expect,(call int_subtract,1,1),0) 387$(call math-expect,(call int_subtract,100,1),99) 388$(call math-expect,(call int_subtract,200,100),100) 389$(call math-expect-error,(call int_subtract,0,1),subtract underflow 0 - 1) 390 391define int_multiply 392$(words $(foreach a,$(call _int_encode,$(1)),$(call _int_encode,$(2)))) 393endef 394 395$(call math-expect,(call int_multiply,0,0),0) 396$(call math-expect,(call int_multiply,1,0),0) 397$(call math-expect,(call int_multiply,1,1),1) 398$(call math-expect,(call int_multiply,100,1),100) 399$(call math-expect,(call int_multiply,1,100),100) 400$(call math-expect,(call int_multiply,4,100),400) 401$(call math-expect,(call int_multiply,100,4),400) 402 403define int_divide 404$(if $(filter 0,$(2)),$(call math-error,division by zero is not allowed!),$(strip \ 405 $(if $(call _int_greater-or-equal,$(call _int_encode,$(1)),$(call _int_encode,$(2))), \ 406 $(call int_plus,$(call int_divide,$(call int_subtract,$(1),$(2)),$(2)),1),0))) 407endef 408 409$(call math-expect,(call int_divide,1,1),1) 410$(call math-expect,(call int_divide,200,1),200) 411$(call math-expect,(call int_divide,200,3),66) 412$(call math-expect,(call int_divide,1,2),0) 413$(call math-expect-error,(call int_divide,0,0),division by zero is not allowed!) 414$(call math-expect-error,(call int_divide,1,0),division by zero is not allowed!) 415 416ifdef RUN_MATH_TESTS 417 ifdef MATH_TEST_FAILURE 418 math-tests: 419 @echo FAIL 420 @false 421 else 422 math-tests: 423 @echo PASS 424 endif 425 .PHONY: math-tests 426endif 427