我正在寻找一种算法，给定自然参数l1, n1, m1, l2, n2, m2和大小，当且仅当存在自然数k1, k2, r1, r2满足以下条件时回答"true"
l1 + k1*m1 + r1 = l2 + k2*m2 + r2
具有k1 <= n1, k2 <= n2, r1 <Size,>
明显解在min(n1, n2)上呈线性。我想找一种更有效率的方法。
<<h2>上下文/h2>我正在尝试在静态分析器中实现C99规则6.5.16.1:3的检查
表示存储在一个对象中的值是从另一个对象中读取的它以任何方式与第一个对象的存储重叠，然后是重叠部分应精确…，否则，行为是定义。
当分析器遇到分配*p1 = *p2;，其中p1和p2可能指向同一块时，必须检查p1和p2所指向的区域不以上述规则禁止的方式重叠。上面的参数"size"对应p1和p2所指向的类型的大小。这个大小是静态已知的。已知p1在块内指向的偏移量表示为l1 + k1*m1，其中l1和m1是固定的，已知的自然整数，k1在0和n1之间变化(n1也是固定且已知的)。类似地，已知p2指向的偏移量对于已知的l2、m2和n2，其形式为l2 + k2*m2。方程l1 + k1*m1 + r1 = l2 + k2*m2 + r2对应于一些重叠偏移的存在。条件r1 <> r2对应于重叠不精确的情况，此时分析器必须发出警告。
似乎你正在寻找一个线性同余系统的解。中国剩余定理应该是适用的。它不会应用你的边界检查，但如果它找到一个解决方案，你可以自己检查边界。
编辑:忘记CRT。
假设size <= m1和size <= m2，将内存区域的低(包含)和高(不包含)边缘建模为线性关系:
addr1low = l1 + k1*m1
addr1high = addr1low + size = l1 + k1*m1 + size
addr2low = l2 + k2*m2
addr2high = addr2low + size = l2 + k2*m2 + size
您想知道addr1low < addr2low < addr1high或addr1low < addr2high < addr1high的范围内是否存在k1, k2。注意排他性不等式;这样我们就避免了正好与重叠。
假设m1 = m2 = m。考虑:
addr1low < addr2low
l1 + k1*m < l2 + k2*m
(k1 - k2) * m < l2 - l1
k1 - k2 < (l2 - l1) / m
addr2low < addr1high
l2 + k2*m < l1 + k1*m + size
l2 - l1 < (k1 - k2) * m + size
(l2 - l1 - size) < (k1 - k2) * m
(l2 - l1 - size) / m < k1 - k2
上述过程是可逆的。假设k1, k2为0，则-n2 <= k1 - k2 <= n1。如果在(l2 - l1 - size) / m和(l2 - l1) / m之间存在整数，则系统保持，并且存在重叠。也就是说，如果ceil(max((l2 - l1 - size) / m, -n2)) <= floor(min((l2 - l1) / m, n1))。另一种情况(addr1low < addr2high < addr1high)的处理方式类似:
addr1low < addr2high
l1 + k1*m < l2 + k2*m + size
// ..
(l1 - l2 - size) / m < k2 - k1
addr2high < addr1high
addr2low + size < addr1low + size
addr2low < addr1low
// ..
k2 - k1 < (l1 - l2) / m
现在测试变成ceil(max((l1 - l2 - size) / m, -n1)) <= floor(min((l1 - l2) / m, n2))。
现在考虑m1 <> m1，在不丧失一般性的情况下，考虑m1 < m2。
将变量视为连续的，求解交点:
addr1low < addr2low
l1 + k*m1 < l2 + k*m2
(l1 - l2) < k * (m2 - m1)
(l1 - l2) / (m2 - m1) < k
addr2low < addr1high
l2 + k*m2 < l1 + k*m1 + size
l2 - l1 - size < k * (m1 - m2)
(l2 - l1 - size) / (m1 - m2) > k // m1 - m2 < 0
同样，步骤是可逆的，因此任何满足边界的整数k < min(n1, n2)都将使系统保持。也就是说，它满足ceil(max((l1 - l2) / (m2 - m1), 0)) <= floor(min((l2 - l1 - size) / (m1 - m2), n1, n2))。另一种情况:
addr1low < addr2high
l1 + k*m1 < l2 + k*m2 + size
l1 - l2 - size < k * (m2 - m1)
(l1 - l2 - size) / (m2 - m1) < k
addr2high < addr1high
addr2low + size < addr1low + size
addr2low < addr1low
l2 + k*m2 < l1 + k*m1
l2 - l1 < k * (m1 - m2)
(l2 - l1) / (m1 - m2) > k // m1 - m2 < 0
这里的测试变成了ceil(max((l1 - l2 - size) / (m2 - m1), 0)) <= floor(min((l2 - l1) / (m1 - m2), n1, n2))。
最终的伪代码可能看起来像这样:
intersectos?(l1, n1, m1, l2, n2, m2, size) {
if (m1 == m2) {
return ceil(max((l2 - l1 - size) / m, -n2)) <= floor(min((l2 - l1) / m, n1)) ||
ceil(max((l1 - l2 - size) / m, -n1)) <= floor(min((l1 - l2) / m, n2));
}
if (m1 > m2) {
swap the arguments
}
return ceil(max((l1 - l2) / (m2 - m1), 0)) <= floor(min((l2 - l1 - size) / (m1 - m2), n1, n2)) ||
ceil(max((l1 - l2 - size) / (m2 - m1), 0)) <= floor(min((l2 - l1) / (m1 - m2), n1, n2));
}
对明显算法
的一个小改进p1和p2的相互排列具有周期性，其周期为lcm(m1, m2) = m1 * m2/gcd(m1, m2)。在最明显的解中，假设你从0到n1遍历k1。由于提到的重复模式，您可以在达到m2/gcd(m1, m2)时立即停止。我假设你已经简化了(l1, n1)到交点。
2。更棘手的方法
让我们重新表述这个问题:p1和p2之间的最小非零距离是否小于size?
首先，让我们考虑p1-p2。然后我们将p2-p1加入混合物。
我们要找到
的最小非零值p1, p2 = (l1 + k1 * m1) - (l2 + k2 *平方米)=(寓于)+ (k1 * m1 - k2 * m2)。
令d = gcd(m1, m2)。如果我们允许k1和k2取任意整数值，则k1*m1 - k2*m2的所有可能值的集合与k*d对任意整数值k的所有可能值的集合完全相同。
因此(l1-l2) + (k1*m1 - k2*m2)的最小非零值是(l1-l2) mod d如果它非零，否则是d。在这里，即使(l1-l2)是负的，mod也给出一个正的结果。
让我们找出最小的这样的k1和k2。扩展欧几里得算法给出a1和a2(可能是负数)，使得d = a1*m1 - a2*m2。解在0 = (m2/d)*m1 - (m1/d)*m2之前是唯一的。
(l1-l2) mod d = (l1-l2) + k * d
(寓于)国防部d =(寓于)+ k * * m1 (a1 - a2 * m2)
(寓于)国防部d =(寓于)+ (k * a1) * m1 - (k * a2) * m2
加减0 = (m2/d)*m1 - (m1/d)*m2足够的次数，使得m1和m2的系数都是正的，并且是最小的。这是第一次给出p2到达p1的位置，距离为(l1-l2) mod d。
如果刚刚发现k1和k2在边界内并且(l1-l2) mod d不为零，那么这个回答是正的。否则，对(l1-l2) mod d + d重复同样的操作，一直重复，直到得到大小。
然后重复p2-p1，而不是p1-p2。
如果所有步骤都没有给出肯定的答案，那么答案是否定的。
算法复杂度为0 (size/gcd(m1, m2))
在每个特定情况下选择哪种算法取决于特定的数字。计算gcd也不自由(O(log(min(m1, m2))))).