← Back to branch summary

~ubuntu-branches/ubuntu/utopic/fftw3/utopic

« back to all changes in this revision

Viewing changes to kernel/tensor7.c

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2011-12-14 13:21:22 UTC
  • mfrom: (3.1.5 sid)
  • Revision ID: package-import@ubuntu.com-20111214132122-l4avyl2kkr7vq5aj
Tags: 3.3-1ubuntu1
* Merge with Debian; remaining changes:
  - Revert the ARM workaround.

Show diffs side-by-side

added added

removed removed

Lines of Context:
kernel/tensor7.c
1
1
/*
2
 
 * Copyright (c) 2003, 2007-8 Matteo Frigo
3
 
 * Copyright (c) 2003, 2007-8 Massachusetts Institute of Technology
 
2
 * Copyright (c) 2003, 2007-11 Matteo Frigo
 
3
 * Copyright (c) 2003, 2007-11 Massachusetts Institute of Technology
4
4
 *
5
5
 * This program is free software; you can redistribute it and/or modify
6
6
 * it under the terms of the GNU General Public License as published by
51
51
     return signof(a->n - b->n);
52
52
}
53
53
 
 
54
static void canonicalize(tensor *x)
 
55
{
 
56
     if (x->rnk > 1) {
 
57
          qsort(x->dims, (size_t)x->rnk, sizeof(iodim),
 
58
                (int (*)(const void *, const void *))X(dimcmp));
 
59
     }
 
60
}
 
61
 
 
62
static int compare_by_istride(const iodim *a, const iodim *b)
 
63
{
 
64
     INT sai = X(iabs)(a->is), sbi = X(iabs)(b->is);
 
65
 
 
66
     /* in descending order of istride */
 
67
     return signof(sbi - sai);
 
68
}
 
69
 
 
70
static tensor *really_compress(const tensor *sz)
 
71
{
 
72
     int i, rnk;
 
73
     tensor *x;
 
74
 
 
75
     A(FINITE_RNK(sz->rnk));
 
76
     for (i = rnk = 0; i < sz->rnk; ++i) {
 
77
          A(sz->dims[i].n > 0);
 
78
          if (sz->dims[i].n != 1)
 
79
               ++rnk;
 
80
     }
 
81
 
 
82
     x = X(mktensor)(rnk);
 
83
     for (i = rnk = 0; i < sz->rnk; ++i) {
 
84
          if (sz->dims[i].n != 1)
 
85
               x->dims[rnk++] = sz->dims[i];
 
86
     }
 
87
     return x;
 
88
}
54
89
 
55
90
/* Like tensor_copy, but eliminate n == 1 dimensions, which
56
91
   never affect any transform or transform vector.
57
92
 
58
93
   Also, we sort the tensor into a canonical order of decreasing
59
 
   is.  In general, processing a loop/array in order of
60
 
   decreasing stride will improve locality; sorting also makes the
61
 
   analysis in fftw_tensor_contiguous (below) easier.  The choice
62
 
   of is over os is mostly arbitrary, and hopefully
63
 
   shouldn't affect things much.  Normally, either the os will be
64
 
   in the same order as is (for e.g. multi-dimensional
65
 
   transforms) or will be in opposite order (e.g. for Cooley-Tukey
66
 
   recursion).  (Both forward and backwards traversal of the tensor
67
 
   are considered e.g. by vrank-geq1, so sorting in increasing
68
 
   vs. decreasing order is not really important.) */
 
94
   strides (see X(dimcmp) for an exact definition).  In general,
 
95
   processing a loop/array in order of decreasing stride will improve
 
96
   locality.  Both forward and backwards traversal of the tensor are
 
97
   considered e.g. by vrank-geq1, so sorting in increasing
 
98
   vs. decreasing order is not really important. */
69
99
tensor *X(tensor_compress)(const tensor *sz)
70
100
{
71
 
     int i, rnk;
72
 
     tensor *x;
73
 
 
74
 
     A(FINITE_RNK(sz->rnk));
75
 
     for (i = rnk = 0; i < sz->rnk; ++i) {
76
 
          A(sz->dims[i].n > 0);
77
 
          if (sz->dims[i].n != 1)
78
 
               ++rnk;
79
 
     }
80
 
 
81
 
     x = X(mktensor)(rnk);
82
 
     for (i = rnk = 0; i < sz->rnk; ++i) {
83
 
          if (sz->dims[i].n != 1)
84
 
               x->dims[rnk++] = sz->dims[i];
85
 
     }
86
 
 
87
 
     if (rnk > 1) {
88
 
          qsort(x->dims, (size_t)x->rnk, sizeof(iodim),
89
 
                (int (*)(const void *, const void *))X(dimcmp));
90
 
     }
91
 
 
 
101
     tensor *x = really_compress(sz);
 
102
     canonicalize(x);
92
103
     return x;
93
104
}
94
105
 
110
121
     if (X(tensor_sz)(sz) == 0) 
111
122
          return X(mktensor)(RNK_MINFTY);
112
123
 
113
 
     sz2 = X(tensor_compress)(sz);
 
124
     sz2 = really_compress(sz);
114
125
     A(FINITE_RNK(sz2->rnk));
115
126
 
116
 
     if (sz2->rnk < 2)          /* nothing to compress */
 
127
     if (sz2->rnk <= 1) { /* nothing to compress. */ 
 
128
          if (0) {
 
129
               /* this call is redundant, because "sz->rnk <= 1" implies
 
130
                  that the tensor is already canonical, but I am writing
 
131
                  it explicitly because "logically" we need to canonicalize
 
132
                  the tensor before returning. */
 
133
               canonicalize(sz2);
 
134
          }
117
135
          return sz2;
118
 
 
 
136
     }
 
137
 
 
138
     /* sort in descending order of |istride|, so that compressible
 
139
        dimensions appear contigously */
 
140
     qsort(sz2->dims, (size_t)sz2->rnk, sizeof(iodim),
 
141
                (int (*)(const void *, const void *))compare_by_istride);
 
142
 
 
143
     /* compute what the rank will be after compression */
119
144
     for (i = rnk = 1; i < sz2->rnk; ++i)
120
145
          if (!strides_contig(sz2->dims + i - 1, sz2->dims + i))
121
146
               ++rnk;
122
147
 
 
148
     /* merge adjacent dimensions whenever possible */
123
149
     x = X(mktensor)(rnk);
124
150
     x->dims[0] = sz2->dims[0];
125
151
     for (i = rnk = 1; i < sz2->rnk; ++i) {
134
160
     }
135
161
 
136
162
     X(tensor_destroy)(sz2);
 
163
 
 
164
     /* reduce to canonical form */
 
165
     canonicalize(x);
137
166
     return x;
138
167
}
139
168