asn1fix_crange.c

RSA加密/解密算法源码 asn1c-0.9.12

		asn1cnst_range_t *r = _range_new();
		r->left = range->left;
		r->right = range->right;
		_range_insert(range, r);
		assert(range->el_count == 1);
	}

	/*
	 * Make sure we're dealing with sane data.
	 * G.4.2.3
	 */
	if(strict_edge_check) {
		for(j = -1; j < with->el_count; j++) {

			if(j == -1) {
				if(with->el_count) continue;
				if(_check_edges_within(range, with))
					return -1;
			} else {
				if(_check_edges_within(range,
						with->elements[j]))
					return -1;
			}
		}
	}

	/*
	 * Split range in pieces.
	 */

	for(i = 0; i < range->el_count; i++) {
	  for(j = -1; j < with->el_count; j++) {
		const asn1cnst_range_t *wel;
		asn1cnst_range_t *r;

		if(j == -1) {
			if(with->el_count) continue;
			wel = with;
		} else {
			wel = with->elements[j];
		}

		r = _range_split(range->elements[i], wel);
		if(r) {
			int ec;
			/* Substitute the current element with a split */
			_range_remove_element(range, i);
			assert(r->el_count);
			for(ec = 0; ec < r->el_count; ec++) {
				ret = _range_insert(range, r->elements[ec]);
				assert(ret == 0);
			}
			r->el_count = 0;
			_range_free(r);
			i--;
			break;	/* Try again from this point */
		}
	  }
	}

	assert(range->el_count);

	/*
	 * Remove pieces which aren't AND-compatible "with" range.
	 */

	for(i = 0; i < range->el_count; i++) {
		for(j = -1; j < with->el_count; j++) {
			const asn1cnst_range_t *wel;
	
			if(j == -1) {
				if(with->el_count) continue;
				wel = with;
			} else {
				wel = with->elements[j];
			}

			if(_range_overlap(range->elements[i], wel))
				break;
		}
		if(j == with->el_count) {
			_range_remove_element(range, i);
			i--;
		}
	}

	if(range->el_count == 0)
		range->empty_constraint = 1;

	return 0;
}

static int
_range_union(asn1cnst_range_t *range) {
	int i;

	qsort(range->elements, range->el_count, sizeof(range->elements[0]),
		_range_compare);

	/*
	 * The range is sorted by the start values.
	 */
	for(i = 1; i < range->el_count; i++) {
		asn1cnst_range_t *ra = range->elements[i - 1];
		asn1cnst_range_t *rb = range->elements[i];

		if(_range_overlap(ra, rb)) {
			if(_edge_compare(&ra->left, &rb->left) < 0)
				rb->left = ra->left;

			if(_edge_compare(&ra->right, &rb->right) > 0)
				rb->right = ra->right;
		} else {
			/*
			 * Still, range may be joined: (1..4)(5..10).
			 * This logic is valid only for whole numbers
			 * (i.e., not REAL type, but REAL constraints
			 * are not PER-visible (X.691, #9.3.12).
			 */
			if(ra->right.type == ARE_VALUE
			&& rb->left.type == ARE_VALUE
			&& (rb->left.value - ra->right.value) == 1) {
				/* (1..10) */
				rb->left = ra->left;
			} else {
				continue;
			}
		}

		/*
		 * Squeeze the array by removing the ra.
		 */
		_range_remove_element(range, i - 1);

		i--;	/* Retry from the current point */
	}

	return 0;
}

static int
_range_canonicalize(asn1cnst_range_t *range) {

	if(range->el_count == 0) {
		/*
		 * Switch left and right edges, make them sorted.
		 * It might be a mild warning though.
		 */
		if(_edge_compare(&range->left, &range->right) > 0) {
			asn1cnst_edge_t tmp = range->left;
			range->left = range->right;
			range->right = tmp;
		}

		if(range->elements) {
			free(range->elements);
			range->elements = 0;
		}
		range->el_size = 0;
		return 0;
	}

	/*
	 * Remove duplicates and overlaps by merging them in.
	 */
	_range_union(range);

	/* Refine the left edge of a parent */
	range->left = range->elements[0]->left;

	/* Refine the right edge of a parent */
	range->right = range->elements[range->el_count - 1]->right;

	/* Remove the child, if it's a single one */
	if(range->el_count == 1) {
		_range_remove_element(range, 0);
	}

	return 0;
}

asn1cnst_range_t *
asn1constraint_compute_PER_range(asn1p_expr_type_e expr_type, const asn1p_constraint_t *ct, enum asn1p_constraint_type_e type, const asn1cnst_range_t *minmax, int *exmet, int strict_PV) {
	asn1cnst_range_t *range;
	asn1cnst_range_t *tmp;
	asn1p_value_t *vmin;
	asn1p_value_t *vmax;
	int expectation_met;
	unsigned int i;
	int ret;

	if(!exmet) {
		exmet = &expectation_met;
		*exmet = 0;
	}

	/*
	 * Check if the requested constraint is theoretically compatible
	 * with the given expression type.
	 */
	if(asn1constraint_compatible(expr_type, type) != 1) {
		errno = EINVAL;
		return 0;
	}

	/* Check arguments' validity. */
	switch(type) {
	case ACT_EL_RANGE:
		if(exmet == &expectation_met)
			*exmet = 1;
		break;
	case ACT_CT_FROM:
		if(!minmax) {
			minmax = asn1constraint_default_alphabet(expr_type);
			if(minmax) {
				break;
			}
		}
		/* Fall through */
	case ACT_CT_SIZE:
		if(!minmax) {
			static asn1cnst_range_t mm;
			mm.left.type = ARE_VALUE;
			mm.left.value = 0;
			mm.right.type = ARE_MAX;
			minmax = &mm;
		}
		break;
	default:
		errno = EINVAL;
		return 0;
	}

	if(minmax) {
		range = _range_clone(minmax);
	} else {
		range = _range_new();
	}

	/*
	 * X.691, #9.3.6
	 * Constraints on restricter character string types
	 * which are not known-multiplier are not PER-visible.
	 */
	if((expr_type & ASN_STRING_NKM_MASK))
		range->not_PER_visible = 1;

	if(!ct || (strict_PV && range->not_PER_visible))
		return range;

	switch(ct->type) {
	case ACT_EL_VALUE:
		vmin = vmax = ct->value;
		break;
	case ACT_EL_RANGE:
	case ACT_EL_LLRANGE:
	case ACT_EL_RLRANGE:
	case ACT_EL_ULRANGE:
		vmin = ct->range_start;
		vmax = ct->range_stop;
		break;
	case ACT_EL_EXT:
		if(!*exmet) {
			range->incompatible = 1;
		} else {
			_range_free(range);
			errno = ERANGE;
			range = 0;
		}
		return range;
	case ACT_CT_SIZE:
	case ACT_CT_FROM:
		if(type == ct->type) {
			*exmet = 1;
		} else {
			range->incompatible = 1;
			return range;
		}
		assert(ct->el_count == 1);
		tmp = asn1constraint_compute_PER_range(expr_type,
			ct->elements[0], type, minmax, exmet, strict_PV);
		if(tmp) {
			_range_free(range);
		} else {
			if(errno == ERANGE) {
				range->empty_constraint = 1;
				range->extensible = 1;
				tmp = range;
			} else {
				_range_free(range);
			}
		}
		return tmp;
	case ACT_CA_SET:	/* (10..20)(15..17) */
	case ACT_CA_INT:	/* SIZE(1..2) ^ FROM("ABCD") */

		/* AND constraints, one after another. */
		for(i = 0; i < ct->el_count; i++) {
			tmp = asn1constraint_compute_PER_range(expr_type,
				ct->elements[i], type,
				ct->type==ACT_CA_SET?range:minmax, exmet,
				strict_PV);
			if(!tmp) {
				if(errno == ERANGE) {
					continue;
				} else {
					_range_free(range);
					return NULL;
				}
			}

			if(tmp->incompatible) {
				/*
				 * Ignore constraints
				 * incompatible with arguments:
				 * 	SIZE(1..2) ^ FROM("ABCD")
				 * either SIZE or FROM will be ignored.
				 */
				_range_free(tmp);
				continue;
			}

			if(strict_PV && tmp->not_PER_visible) {
				if(ct->type == ACT_CA_SET) {
					/*
					 * X.691, #9.3.18:
					 * Ignore this separate component.
					 */
				} else {
					/*
					 * X.691, #9.3.19:
					 * Ignore not PER-visible INTERSECTION
					 */
				}
				_range_free(tmp);
				continue;
			}

			ret = _range_intersection(range, tmp,
				ct->type == ACT_CA_SET);
			_range_free(tmp);
			if(ret) {
				_range_free(range);
				errno = EPERM;
				return NULL;
			}
			_range_canonicalize(range);
		}

		return range;
	case ACT_CA_CSV:	/* SIZE(1..2, 3..4) */
	case ACT_CA_UNI:	/* SIZE(1..2) | FROM("ABCD") */

		/*
		 * Grab the first valid constraint.
		 */
		tmp = 0;
		for(i = 0; i < ct->el_count; i++) {
			tmp = asn1constraint_compute_PER_range(expr_type,
				ct->elements[i], type, minmax, exmet,
				strict_PV);
			if(!tmp) {
				if(errno == ERANGE) {
					range->extensible = 1;
					continue;
				} else {
					_range_free(range);
					return NULL;
				}
			}
			if(tmp->incompatible) {
				_range_free(tmp);
				tmp = 0;
			}
			break;
		}
		if(tmp) {
			tmp->extensible |= range->extensible;
			tmp->empty_constraint |= range->empty_constraint;
			_range_free(range);
			range = tmp;
		} else {
			range->incompatible = 1;
			return range;
		}

		/*
		 * Merge with the rest of them.
		 * Canonicalizator will do the union magic.
		 */
		for(; i < ct->el_count; i++) {
			tmp = asn1constraint_compute_PER_range(expr_type,
				ct->elements[i], type, minmax, exmet,
				strict_PV);
			if(!tmp) {
				if(errno == ERANGE) {
					range->extensible = 1;
					continue;
				} else {
					_range_free(range);
					return NULL;
				}
			}

			if(tmp->incompatible) {
				_range_free(tmp);
				_range_canonicalize(range);
				range->incompatible = 1;
				return range;
			}

			if(tmp->empty_constraint) {
				/*
				 * Ignore empty constraints in OR logic.
				 */
				range->extensible |= tmp->extensible;
				_range_free(tmp);
				continue;
			}

			_range_merge_in(range, tmp);
		}

		_range_canonicalize(range);

		if(range->extensible && type == ACT_CT_FROM) {
			/*
			 * X.691, #9.3.10:
			 * Extensible permitted alphabet constraints
			 * are not PER-visible.
			 */
			range->not_PER_visible = 1;
		}

		if(strict_PV && range->not_PER_visible) {
			/*
			 * X.691, #9.3.19:
			 * If not PER-visible constraint is part of UNION,
			 * the whole resulting constraint is not PER-visible.
			 */
			_range_free(range);
			if(minmax)
				range = _range_clone(minmax);
			else
				range = _range_new();
			range->not_PER_visible = 1;
			range->incompatible = 1;
		}

		return range;
	case ACT_CA_EXC:	/* FROM("ABCD") EXCEPT FROM("AB") */
		/*
		 * X.691, #9.3.19:
		 * EXCEPT and the following value set is completely ignored.
		 */
		assert(ct->el_count >= 1);
		_range_free(range);
		range = asn1constraint_compute_PER_range(expr_type,
			ct->elements[0], type, minmax, exmet, strict_PV);
		return range;
	default:
		range->incompatible = 1;
		return range;
	}


	if(!*exmet) {
		/*
		 * Expectation is not met. Return the default range.
		 */
		range->incompatible = 1;
		return range;
	}

	_range_free(range);
	range = _range_new();

	ret  = _range_fill(vmin, minmax, &range->left,
				range, type, ct->_lineno);
	if(!ret)
	ret = _range_fill(vmax, minmax, &range->right,
				range, type, ct->_lineno);
	if(ret) {
		_range_free(range);
		errno = EPERM;
		return NULL;
	}

	if(minmax) {
		asn1cnst_range_t *clone;

		clone = _range_clone(minmax);

		/* Constrain parent type with given data. */
		ret = _range_intersection(clone, range, 1);
		_range_free(range);
		if(ret) {
			_range_free(clone);
			errno = EPERM;
			return NULL;
		}
		range = clone;
	}

	/*
	 * Recompute elements's min/max, remove duplicates, etc.
	 */
	_range_canonicalize(range);

	return range;
}