f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * ***** BEGIN LICENSE BLOCK *****
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Version: MPL 1.1/GPL 2.0/LGPL 2.1
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The contents of this file are subject to the Mozilla Public License Version
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * 1.1 (the "License"); you may not use this file except in compliance with
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the License. You may obtain a copy of the License at
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Software distributed under the License is distributed on an "AS IS" basis,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * for the specific language governing rights and limitations under the
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The Original Code is the Multi-precision Binary Polynomial Arithmetic Library.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The Initial Developer of the Original Code is
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Sun Microsystems, Inc.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Portions created by the Initial Developer are Copyright (C) 2003
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the Initial Developer. All Rights Reserved.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Contributor(s):
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Sheueling Chang Shantz <sheueling.chang@sun.com> and
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Douglas Stebila <douglas@stebila.ca> of Sun Laboratories.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Alternatively, the contents of this file may be used under the terms of
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * either the GNU General Public License Version 2 or later (the "GPL"), or
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * in which case the provisions of the GPL or the LGPL are applicable instead
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * of those above. If you wish to allow use of your version of this file only
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * under the terms of either the GPL or the LGPL, and not to allow others to
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * use your version of this file under the terms of the MPL, indicate your
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * decision by deleting the provisions above and replace them with the notice
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * and other provisions required by the GPL or the LGPL. If you do not delete
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the provisions above, a recipient may use your version of this file under
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the terms of any one of the MPL, the GPL or the LGPL.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * ***** END LICENSE BLOCK ***** */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Use is subject to license terms.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Sun elects to use this software under the MPL license.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#pragma ident "%Z%%M% %I% %E% SMI"
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Multiply two binary polynomials mp_digits a, b.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Result is a polynomial with degree < 2 * MP_DIGIT_BITS - 1.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Output in two mp_digits rh, rl.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowerss_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers register mp_digit h, l, s;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers tab[4] = a4; tab[5] = a1^a4; tab[6] = a2^a4; tab[7] = a1^a2^a4;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 12 & 0x7]; l ^= s << 12; h ^= s >> 20;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 15 & 0x7]; l ^= s << 15; h ^= s >> 17;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 18 & 0x7]; l ^= s << 18; h ^= s >> 14;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 21 & 0x7]; l ^= s << 21; h ^= s >> 11;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* compensate for the top two bits of a */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowerss_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers register mp_digit h, l, s;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers tab[ 0] = 0; tab[ 1] = a1; tab[ 2] = a2; tab[ 3] = a1^a2;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers tab[ 4] = a4; tab[ 5] = a1^a4; tab[ 6] = a2^a4; tab[ 7] = a1^a2^a4;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers tab[ 8] = a8; tab[ 9] = a1^a8; tab[10] = a2^a8; tab[11] = a1^a2^a8;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers tab[12] = a4^a8; tab[13] = a1^a4^a8; tab[14] = a2^a4^a8; tab[15] = a1^a2^a4^a8;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 12 & 0xF]; l ^= s << 12; h ^= s >> 52;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 16 & 0xF]; l ^= s << 16; h ^= s >> 48;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 20 & 0xF]; l ^= s << 20; h ^= s >> 44;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 24 & 0xF]; l ^= s << 24; h ^= s >> 40;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 28 & 0xF]; l ^= s << 28; h ^= s >> 36;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 32 & 0xF]; l ^= s << 32; h ^= s >> 32;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 36 & 0xF]; l ^= s << 36; h ^= s >> 28;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 40 & 0xF]; l ^= s << 40; h ^= s >> 24;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 44 & 0xF]; l ^= s << 44; h ^= s >> 20;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 48 & 0xF]; l ^= s << 48; h ^= s >> 16;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s = tab[b >> 52 & 0xF]; l ^= s << 52; h ^= s >> 12;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* compensate for the top three bits of a */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Compute xor-multiply of two binary polynomials (a1, a0) x (b1, b0)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * result is a binary polynomial in 4 mp_digits r[4].
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The caller MUST ensure that r has the right amount of space allocated.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowerss_bmul_2x2(mp_digit *r, const mp_digit a1, const mp_digit a0, const mp_digit b1,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers r[2] ^= m1 ^ r[1] ^ r[3]; /* h0 ^= m1 ^ l1 ^ h1; */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers r[1] = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0; /* l1 ^= l0 ^ h0 ^ m0; */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Compute xor-multiply of two binary polynomials (a2, a1, a0) x (b2, b1, b0)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * result is a binary polynomial in 6 mp_digits r[6].
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The caller MUST ensure that r has the right amount of space allocated.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowerss_bmul_3x3(mp_digit *r, const mp_digit a2, const mp_digit a1, const mp_digit a0,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers const mp_digit b2, const mp_digit b1, const mp_digit b0)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s_bmul_1x1(r+5, r+4, a2, b2); /* fill top 2 words */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s_bmul_2x2(zm, a1, a2^a0, b1, b2^b0); /* fill middle 4 words */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s_bmul_2x2(r, a1, a0, b1, b0); /* fill bottom 4 words */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Compute xor-multiply of two binary polynomials (a3, a2, a1, a0) x (b3, b2, b1, b0)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * result is a binary polynomial in 8 mp_digits r[8].
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * The caller MUST ensure that r has the right amount of space allocated.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersvoid s_bmul_4x4(mp_digit *r, const mp_digit a3, const mp_digit a2, const mp_digit a1,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers const mp_digit a0, const mp_digit b3, const mp_digit b2, const mp_digit b1,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s_bmul_2x2(r+4, a3, a2, b3, b2); /* fill top 4 words */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s_bmul_2x2(zm, a3^a1, a2^a0, b3^b1, b2^b0); /* fill middle 4 words */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s_bmul_2x2(r, a1, a0, b1, b0); /* fill bottom 4 words */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Compute addition of two binary polynomials a and b,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * store result in c; c could be a or b, a and b could be equal;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * c is the bitwise XOR of a and b.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_badd(const mp_int *a, const mp_int *b, mp_int *c)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* Add all digits up to the precision of b. If b had more
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * precision than a initially, swap a, b first
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* Make sure c has enough precision for the output value */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* Do word-by-word xor */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* Finish the rest of digits until we're actually done */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers#define s_mp_div2(a) MP_CHECKOK( mpl_rsh((a), (a), 1) );
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Compute binary polynomial multiply d = a * b */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowerss_bmul_d(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Compute binary polynomial xor multiply accumulate d ^= a * b */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowerss_bmul_d_add(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Compute binary polynomial xor multiply c = a * b.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * All parameters may be identical.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_bmul(const mp_int *a, const mp_int *b, mp_int *c)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers if (a == c) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers if (a == b)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers } else if (b == c) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers const mp_int *xch = b; /* switch a and b if b longer */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s_bmul_d(MP_DIGITS(a), MP_USED(a), *pb++, MP_DIGITS(c));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* Outer loop: Digits of b */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* Inner product: Digits of a */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers s_bmul_d_add(MP_DIGITS(a), a_used, b_i, MP_DIGITS(c) + ib);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Compute modular reduction of a and store result in r.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * r could be a.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * For modular arithmetic, the irreducible polynomial f(t) is represented
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * as an array of int[], where f(t) is of the form:
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * f(t) = t^p[0] + t^p[1] + ... + t^p[k]
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * where m = p[0] > p[1] > ... > p[k] = 0.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_bmod(const mp_int *a, const unsigned int p[], mp_int *r)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* The algorithm does the reduction in place in r,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * if a != r, copy a into r first so reduction can be done in r
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers if (a != r) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* start reduction */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers if (zz == 0) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers j--; continue;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for (k = 1; p[k] > 0; k++) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* reducing component t^p[k] */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers n = p[0] - p[k];
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* reducing component t^0 */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* final round of reduction */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers while (j == dN) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers if (zz == 0) break;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* clear up the top d1 bits */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for (k = 1; p[k] > 0; k++) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* reducing component t^p[k]*/
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Compute the product of two polynomials a and b, reduce modulo p,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Store the result in r. r could be a or b; a could be b.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_bmulmod(const mp_int *a, const mp_int *b, const unsigned int p[], mp_int *r)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers if (a == b) return mp_bsqrmod(a, p, r);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers return mp_bmod(r, p, r);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Compute binary polynomial squaring c = a*a mod p .
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Parameter r and a can be identical.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_bsqrmod(const mp_int *a, const unsigned int p[], mp_int *r)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers if (a == r) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Compute binary polynomial y/x mod p, y divided by x, reduce modulo p.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Store the result in r. r could be x or y, and x could equal y.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Uses algorithm Modular_Division_GF(2^m) from
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * the Great Divide".
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_bdivmod(const mp_int *y, const mp_int *x, const mp_int *pp,
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers const unsigned int p[], mp_int *r)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers mp_int *a, *b, *u, *v;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* reduce x and y mod p */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers while (!mp_isodd(a)) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers if (mp_cmp_mag(b, a) > 0) {
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers } while (!mp_isodd(b));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers else if ((MP_DIGIT(a,0) == 1) && (MP_USED(a) == 1))
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers } while (!mp_isodd(a));
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers } while (1);
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers /* XXX this appears to be a memory leak in the NSS code */
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Convert the bit-string representation of a polynomial a into an array
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * of integers corresponding to the bits with non-zero coefficient.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * Up to max elements of the array will be filled. Return value is total
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * number of coefficients that would be extracted if array was large enough.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowersmp_bpoly2arr(const mp_int *a, unsigned int p[], int max)
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers int i, j, k;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for (k = 0; k < max; k++) p[k] = 0;
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers/* Convert the coefficient array representation of a polynomial to a
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers * bit-string. The array must be terminated by 0.
f9fbec18f5b458b560ecf45d3db8e8bd56bf6942mcpowers for (i = 0; p[i] > 0; i++) {