[Matrix-SIG] 2D kernel convolution

[David Ascher]

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.
  Send mail to mime@docserver.cac.washington.edu for more info.

--1900032184-2002504639-891029205=:26832
Content-Type: TEXT/PLAIN; charset=US-ASCII

Well, I got circular convolution to apparently work, but I'm quite baffled
as to why linear convolution doesn't work.

For a simple yet sufficient description of these things, look at 
http://tierra.ciens.ucv.ve/dipcourse/html/linear/convolution/front-page.html


I'm attaching the module here so that folks can

#1) use it if they only need circular convolution
#2) tell me why linear convolution doesn't work
#3) optimize it if they wish (I'd rather #2) happened first -- it's hard
    to modify optimized code...

--david


--1900032184-2002504639-891029205=:26832
Content-Type: TEXT/PLAIN; charset=US-ASCII; name="kconvmodule.c"
Content-Transfer-Encoding: BASE64
Content-ID: <Pine.SUN.3.96.980327120645.26832G@skivs.ski.org>
Content-Description: 

I2luY2x1ZGUgPHN0cmluZy5oPg0KI2luY2x1ZGUgPG1hdGguaD4NCiNpbmNs
dWRlIDxzdGRpby5oPg0KI2luY2x1ZGUgIlB5dGhvbi5oIg0KI2luY2x1ZGUg
ImFycmF5b2JqZWN0LmgiDQoNDQpzdGF0aWMgUHlPYmplY3QgKkVycm9yT2Jq
ZWN0Ow0KDQojZGVmaW5lIFRSWShFKSBpZighIChFKSkgcmV0dXJuIE5VTEwN
CiNkZWZpbmUgQVNTRVJUKEUsTSkgaWYoIShFKSkgcmV0dXJuIEVycm9yUmV0
dXJuKE0pDQoNCnN0YXRpYyBjaGFyIGRvY19kY29udltdID0NDQoiZGNvbnYo
bSwgaywgKHgseSksfCBjaXJjKSB3aWxsIHJldHVybiBhIG1hdHJpeCBvZiB0
aGUgc2FtZSBcbiJcDQ0KImRpbWVuc2lvbnMgYXMgbSB3aGljaCBpcyB0aGUg
cmVzdWx0IG9mIHRoZSBjb252b2x1dGlvbiBvZiBtIHdpdGggdGhlXG4iXA0N
CiJrZXJuZWwgay4gIG0gYW5kIGsgbmVlZCB0byBiZSBhcnJheXMgb2YgZG91
Ymxlcy5cbiJcDQ0KIlRoZSB0aGlyZCBhcmd1bWVudCBpcyB0aGUgb3JpZ2lu
IG9mIHRoZSBrZXJuZWwgKGFrYSBzd2VldCBzcG90KS5cbiJcDQ0KIlRoZSBs
YXN0IG9wdGlvbmFsIGFyZ3VtZW50IGlzIGEgbnVtYmVyICgwIGJ5IGRlZmF1
bHQpLiAgSWYgdGhhdFxuIlwNDQoibnVtYmVyIGlzIG5vbi16ZXJvLCBhIGNp
cmN1bGFyIGNvbnZvbHV0aW9uIGlzIHBlcmZvcm1lZC5cbiJcDQ0KIk90aGVy
d2lzZSBhIGxpbmVhciBjb252b2x1dGlvbiBpcyBwZXJmb3JtZWQuXG4iXA0N
CiJcblxuTk9URTogQ3VycmVudGx5IG9ubHkgY2lyY3VsYXIgY29udm9sdXRp
b24gYXBwZWFycyB0byB3b3JrISEhXG4iOw0KDQpzdGF0aWMgUHlPYmplY3Qg
Kmtjb252X2Rjb252KFB5T2JqZWN0ICppZ25vcmVkLCBQeU9iamVjdCAqYXJn
cykgew0KDQ0KCVB5T2JqZWN0ICpvcCwgKmtwOw0KCVB5QXJyYXlPYmplY3Qg
KmltYWdlLCAqa2VybmVsLCAqY29udm9sdXRpb247DQoNCglkb3VibGUgKmlE
YXRhOw0KCWRvdWJsZSAqa0RhdGE7DQ0KCWRvdWJsZSAqY0RhdGE7DQ0KCWRv
dWJsZSBjdW12YWw7DQ0KDQoJaW50IHNYLCBzWTsgICAvKiBzd2VldCBzcG90
IGNvb3JkaW5hdGVzIGZvciB0aGUga2VybmVsICovDQoJaW50IGlXaWR0aCwg
aUhlaWdodCwga1dpZHRoLCBrSGVpZ2h0LCBjSGVpZ2h0LCBjV2lkdGg7DQoJ
aW50IGtYLCBrWSwgY1gsIGNZLCBpWCwgaVk7DQoJaW50IGNpcmN1bGFyID0g
MDsgIC8qIGJ5IGRlZmF1bHQgZG8gbGluZWFyIGNvbnZvbHV0aW9uICovDQoJ
aW50IGtJbmRleCwgaUluZGV4LCBjSW5kZXg7DQoNCglUUlkoUHlBcmdfUGFy
c2VUdXBsZShhcmdzLCAiT08oaWkpfGkiLCAmb3AsICZrcCwgJnNYLCAmc1ks
ICZjaXJjdWxhcikpOw0KCVRSWShQeUFycmF5X0NoZWNrKG9wKSk7DQoJaW1h
Z2UgPSAoUHlBcnJheU9iamVjdCAqKW9wOw0KCVRSWShQeUFycmF5X0NoZWNr
KGtwKSk7DQoJa2VybmVsID0gKFB5QXJyYXlPYmplY3QgKilrcDsNCglpZiAo
aW1hZ2UtPmRlc2NyLT50eXBlX251bSAhPSBQeUFycmF5X0RPVUJMRSB8fA0K
CSAgICBrZXJuZWwtPmRlc2NyLT50eXBlX251bSAhPSBQeUFycmF5X0RPVUJM
RSkgew0KCQlQeUVycl9TZXRTdHJpbmcoUHlFeGNfVmFsdWVFcnJvciwiYm90
aCBhcnJheXMgbXVzdCBiZSBhcnJheXMgb2YgZG91YmxlcyIpOyAgICAgIA0K
CQlyZXR1cm4gTlVMTDsNCgl9DQoJaWYgKGltYWdlLT5uZCAhPSAyIHx8DQoJ
ICAgIGtlcm5lbC0+bmQgIT0gMikgew0KCQlQeUVycl9TZXRTdHJpbmcoUHlF
eGNfVmFsdWVFcnJvciwiYm90aCBhcnJheXMgbXVzdCBiZSBhcnJheXMgb2Yg
cmFuayAyIik7ICAgICAgDQoJCXJldHVybiBOVUxMOw0KCX0NCglpZiAoY2ly
Y3VsYXIpIHsgLyogY2lyY3VsYXIgY29udm9sdXRpb24gKi8NCgkJY29udm9s
dXRpb24gPSAoUHlBcnJheU9iamVjdCAqKVB5QXJyYXlfRnJvbURpbXMoaW1h
Z2UtPm5kLCBpbWFnZS0+ZGltZW5zaW9ucywgaW1hZ2UtPmRlc2NyLT50eXBl
X251bSk7DQoJfSBlbHNlIHsgIC8qIGxpbmVhciBjb252b2x1dGlvbiAqLw0K
CQlpbnQgZGltc1syXTsNCgkJZGltc1swXSA9IGltYWdlLT5kaW1lbnNpb25z
WzBdICsga2VybmVsLT5kaW1lbnNpb25zWzBdIC0gMTsgDQ0KCQlkaW1zWzFd
ID0gaW1hZ2UtPmRpbWVuc2lvbnNbMV0gKyBrZXJuZWwtPmRpbWVuc2lvbnNb
MV0gLSAxOyANDQoJCWNvbnZvbHV0aW9uID0gKFB5QXJyYXlPYmplY3QgKilQ
eUFycmF5X0Zyb21EaW1zKGltYWdlLT5uZCwgZGltcywgaW1hZ2UtPmRlc2Ny
LT50eXBlX251bSk7DQoJfQ0KCWlmIChjb252b2x1dGlvbiA9PSBOVUxMKSB7
DQoJICBQeUVycl9TZXRTdHJpbmcoUHlFeGNfTWVtb3J5RXJyb3IsIkNvdWxk
bid0IGNyZWF0ZSByZXN1bHQgYXJyYXkiKTsgICAgICANCgkgIHJldHVybiBO
VUxMOw0KCX0NCglpV2lkdGggPSBpbWFnZS0+ZGltZW5zaW9uc1sxXTsgIA0N
CglpSGVpZ2h0ID0gaW1hZ2UtPmRpbWVuc2lvbnNbMF07ICANDQoJa1dpZHRo
ID0ga2VybmVsLT5kaW1lbnNpb25zWzFdOyAgDQ0KCWtIZWlnaHQgPSBrZXJu
ZWwtPmRpbWVuc2lvbnNbMF07ICANDQoJY1dpZHRoID0gY29udm9sdXRpb24t
PmRpbWVuc2lvbnNbMV07ICANDQoJY0hlaWdodCA9IGNvbnZvbHV0aW9uLT5k
aW1lbnNpb25zWzBdOyAgDQ0KDQ0KCWlEYXRhID0gKGRvdWJsZSAqKWltYWdl
LT5kYXRhOw0KCWtEYXRhID0gKGRvdWJsZSAqKWtlcm5lbC0+ZGF0YTsNDQoJ
Y0RhdGEgPSAoZG91YmxlICopY29udm9sdXRpb24tPmRhdGE7DQ0KDQ0KCS8q
IGl0ZXJhdGUgb3ZlciBldmVyeSBsaW5lIGluIHRoZSBjb252ICovDQogICAg
ICAgIGZvciAoY1kgPSAwOyBjWSA8IGNIZWlnaHQ7IGNZKyspIHsNDQoJCS8q
IGl0ZXJhdGUgb3ZlciBldmVyeSBwaXhlbCBpbiBlYWNoIGxpbmUgb2YgdGhl
IGNvbnYgKi8NCgkJZm9yIChjWCA9IDA7IGNYIDwgY1dpZHRoOyBjWCsrKSB7
DQ0KCQkJLyogaXRlcmF0ZSBvdmVyIGV2ZXJ5IGxpbmUgaW4gdGhlIGtlcm5l
bCAqLw0NCgkJCWN1bXZhbCA9IDAuMDsNDQoJCQlmb3IgKGtZID0gMDsga1kg
PCBrSGVpZ2h0OyBrWSsrKSB7DQoJCQkJLyogZmluZCB0aGUgcm93ICMgZm9y
IHRoYXQga2VybmVsIHJvdyBpbiB0aGUgaW1hZ2UgKi8NDQoJCQkJZm9yIChr
WCA9IDA7IGtYIDwga1dpZHRoOyBrWCsrKSB7DQ0KCQkJCQlpWSA9IGNZICsg
a1kgLSBzWTsNDQoJCQkJCWlYID0gY1ggKyBrWCAtIHNYOw0NCgkJCQkJaWYg
KGNpcmN1bGFyKSB7DQ0KCQkJCQkJaWYgKGlZID49IGlIZWlnaHQpIGlZID0g
aVkgLSBpSGVpZ2h0Ow0NCgkJCQkJCWVsc2UgaWYgKGlZIDwgMCkgICBpWSA9
IGlZICsgaUhlaWdodDsNDQoJCQkJCQlpZiAoaVggPj0gaVdpZHRoKSAgaVgg
PSBpWCAtIGlXaWR0aDsNDQoJCQkJCQllbHNlIGlmIChpWCA8IDApICAgaVgg
PSBpWCArIGlXaWR0aDsNDQoJCQkJCX0NDQoJCQkJCWlmIChjaXJjdWxhciB8
fCAoaVkgPj0gMCAmJiBpWSA8IGlIZWlnaHQgJiYgaVggPj0gMCAmJiBpWCA8
IGlXaWR0aCkpIHsNDQoJCQkJCQlrSW5kZXggPSBrWCArIGtZICoga1dpZHRo
Ow0NCgkJCQkJCWlJbmRleCA9IGlYICsgaVkgKiBpV2lkdGg7DQ0KCQkJCQkJ
aWYgKGlJbmRleCA+PSAwICYmIGlJbmRleCA8IGlXaWR0aCAqIGlIZWlnaHQg
JiYNDQoJCQkJCQkgICAga0luZGV4ID49IDAgJiYga0luZGV4IDwga1dpZHRo
ICoga0hlaWdodCkgew0NCgkJCQkJCQljdW12YWwgKz0gaURhdGFbaUluZGV4
XSAqIGtEYXRhW2tJbmRleF07DQ0KCQkJCQkJfQ0NCgkJCQkJfQ0KCQkJCX0N
CgkJCX0NDQoJCQljSW5kZXggPSBjWCArIGNZICogY1dpZHRoOw0NCgkJCWNE
YXRhW2NJbmRleF0gPSBjdW12YWw7DQ0KCQl9DQoJfQ0NCglyZXR1cm4gKFB5
T2JqZWN0ICopY29udm9sdXRpb247DQp9DQoNCnN0YXRpYyBzdHJ1Y3QgUHlN
ZXRob2REZWYga2NvbnZfbWV0aG9kc1tdID0gew0KICB7ImRjb252Iiwga2Nv
bnZfZGNvbnYsIDEsIGRvY19kY29udn0sDQogIHtOVUxMLAkJTlVMTCwgMH0J
CS8qIHNlbnRpbmVsICovDQp9Ow0KDQp2b2lkIGluaXRrY29udigpIHsNCiAg
UHlPYmplY3QgKm07DQogIC8qIENyZWF0ZSB0aGUgbW9kdWxlIGFuZCBhZGQg
dGhlIGZ1bmN0aW9ucyAqLw0KICBpbXBvcnRfYXJyYXkoKTsNCiAgbSA9IFB5
X0luaXRNb2R1bGUoImtjb252Iiwga2NvbnZfbWV0aG9kcyk7DQogIC8qIENo
ZWNrIGZvciBlcnJvcnMgKi8NCiAgaWYgKFB5RXJyX09jY3VycmVkKCkpDQog
ICAgUHlfRmF0YWxFcnJvcigiY2FuJ3QgaW5pdGlhbGl6ZSBtb2R1bGUga2Nv
bnYiKTsNCn0NCg==
--1900032184-2002504639-891029205=:26832--