* Determine whether two arrays share some memory. * * Returns: 0 (no shared memory), 1 (shared memory), or < 0 (failed to solve). * * Note that failures to solve can occur due to integer overflows, or effort * required solving the problem exceeding max_work. The general problem is * NP-hard and worst case runtime is exponential in the number of dimensions. * max_work controls the amount of
| 755 | * max_work > 0 for the number of solution candidates considered. |
| 756 | */ |
| 757 | NPY_VISIBILITY_HIDDEN mem_overlap_t |
| 758 | solve_may_share_memory(PyArrayObject *a, PyArrayObject *b, |
| 759 | Py_ssize_t max_work) |
| 760 | { |
| 761 | npy_int64 rhs; |
| 762 | diophantine_term_t terms[2*NPY_MAXDIMS + 2]; |
| 763 | npy_uintp start1 = 0, end1 = 0, size1 = 0; |
| 764 | npy_uintp start2 = 0, end2 = 0, size2 = 0; |
| 765 | npy_uintp uintp_rhs; |
| 766 | npy_int64 x[2*NPY_MAXDIMS + 2]; |
| 767 | unsigned int nterms; |
| 768 | |
| 769 | get_array_memory_extents(a, &start1, &end1, &size1); |
| 770 | get_array_memory_extents(b, &start2, &end2, &size2); |
| 771 | |
| 772 | if (!(start1 < end2 && start2 < end1 && start1 < end1 && start2 < end2)) { |
| 773 | /* Memory extents don't overlap */ |
| 774 | return MEM_OVERLAP_NO; |
| 775 | } |
| 776 | |
| 777 | if (max_work == 0) { |
| 778 | /* Too much work required, give up */ |
| 779 | return MEM_OVERLAP_TOO_HARD; |
| 780 | } |
| 781 | |
| 782 | /* Convert problem to Diophantine equation form with positive coefficients. |
| 783 | The bounds computed by offset_bounds_from_strides correspond to |
| 784 | all-positive strides. |
| 785 | |
| 786 | start1 + sum(abs(stride1)*x1) |
| 787 | == start2 + sum(abs(stride2)*x2) |
| 788 | == end1 - 1 - sum(abs(stride1)*x1') |
| 789 | == end2 - 1 - sum(abs(stride2)*x2') |
| 790 | |
| 791 | <=> |
| 792 | |
| 793 | sum(abs(stride1)*x1) + sum(abs(stride2)*x2') |
| 794 | == end2 - 1 - start1 |
| 795 | |
| 796 | OR |
| 797 | |
| 798 | sum(abs(stride1)*x1') + sum(abs(stride2)*x2) |
| 799 | == end1 - 1 - start2 |
| 800 | |
| 801 | We pick the problem with the smaller RHS (they are non-negative due to |
| 802 | the extent check above.) |
| 803 | */ |
| 804 | |
| 805 | uintp_rhs = MIN(end2 - 1 - start1, end1 - 1 - start2); |
| 806 | if (uintp_rhs > NPY_MAX_INT64) { |
| 807 | /* Integer overflow */ |
| 808 | return MEM_OVERLAP_OVERFLOW; |
| 809 | } |
| 810 | rhs = (npy_int64)uintp_rhs; |
| 811 | |
| 812 | nterms = 0; |
| 813 | if (strides_to_terms(a, terms, &nterms, 1)) { |
| 814 | return MEM_OVERLAP_OVERFLOW; |
no test coverage detected