[ODE] Space additions for dRay

[David McClurg]

This is a multi-part message in MIME format.

------_=_NextPart_001_01C248CA.2E39C162
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

Erwin-- did your space locking stuff ever get posted?  I'd very much =
like to look at this.

Also, I have a patch for a Tri-list vs Ray collider if you want it.  See =
the attached file and just look at the int =
dcTriListCollider::CollideRay() function.

Ta

-----Original Message-----
From: Erwin de Vries [mailto:erwin@vo.com]
Sent: Monday, 5 August 2002 5:33 AM
To: ode@q12.org
Subject: [ODE] Space additions for dRay


Hi,

Today i've added some new stuff to the space. (Hash & simple) The =
concept is
'locking' the space. A locked space is a space where no modifications to
itself and the geometries it contains are allowed. Internally the =
space_aabb
pointers are calculated once in a Lock()/Unlock() sequence. Nested
lock/unlock pairs are not allowed.

It can be used to do instant collision detection for (but not limited =
to)
rays with minimal overhead.

The implementation is as follows:

// Puts the space in locked mode.
void dSpaceLock (dSpaceID space);

// Collides a single geometry with the other geometries in the space
void dSpaceCollideGeom (dSpaceID space, dxGeom* g, void *data, =
dNearCallback
*callback);

// Puts the space back in normal mode.
void dSpaceUnlock (dSpaceID space);

// Tells whether the space is currently locked.
int dSpaceLocked(dSpaceID space);

Thats it. These functions do not interfere with current behavior, so it =
is
all backwards compatible.

A current problem is dBodySetPosition(), etc. Unlike =
dGeomSetPostition(),
etc, we cant assert these, because there is no telling which geometries
point to a body's data. I dont have a good solution to this problem. =
What
would be possible is to regenerate a list of AABB's in the =
dSpaceUnlock()
function, and compare it to the one generated in the previous =
dSpaceLock().
If they dont match, assert. Only in debugmode of course.

I'll post this soon. Would you like to add this to the core code, Russ? =
I
just created it, so i havent tested it much, but i will do so the next =
days
It passes the space test incuded with ODE. Internally i had to change =
some
things in the hashspace. It now uses buffered allocations (using dArray)
instead of stack allocations for the lists of objects, which of course =
might
be a little slower, and certainly uses more memory. But i've not yet =
tested
how much. Couldnt be -that- much.

Erwin



_______________________________________________
ODE mailing list
ODE@q12.org
http://q12.org/mailman/listinfo/ode

------_=_NextPart_001_01C248CA.2E39C162
Content-Type: application/octet-stream;
	name="dcTriListCollider.cpp"
Content-Transfer-Encoding: base64
Content-Description: dcTriListCollider.cpp
Content-Disposition: attachment;
	filename="dcTriListCollider.cpp"

Ly8gRG8gTk9UIGJ1aWxkIHRoaXMgZmlsZSBzZXBlcmF0ZWx5LiBJdCBpcyBpbmNsdWRlZCBpbiBk
VHJpTGlzdC5jcHAgYXV0b21hdGljYWxseS4NCiNpbmNsdWRlICJhcnJheS5oIg0KI2luY2x1ZGUg
ImR4VHJpTGlzdC5oIg0KI2luY2x1ZGUgImRjVHJpTGlzdENvbGxpZGVyLmgiDQoNCiNpbmNsdWRl
ICJvcGNvZGUvb3Bjb2RlLmgiDQovL3VzaW5nIG5hbWVzcGFjZSBPcGNvZGU7DQojaW5jbHVkZSAi
ZGNBQUJCQ29sbGlkZXIuaCINCiNpbmNsdWRlICJkY09CQkNvbGxpZGVyLmgiDQojaW5jbHVkZSAi
b2RlL2RSYXkuaCINCg0KLy8jZGVmaW5lIEdFTkVSQVRFQk9ESUVTDQoNCmRjVHJpTGlzdENvbGxp
ZGVyOjpkY1RyaUxpc3RDb2xsaWRlcihkeEdlb20qIEdlb21ldHJ5KSA6IEFBQkJDb2xsaWRlcihW
ZXJ0aWNlcywgSW5kaWNlcyksIE9CQkNvbGxpZGVyKFZlcnRpY2VzLCBJbmRpY2VzKXsNCgl0aGlz
LT5HZW9tZXRyeSA9IEdlb21ldHJ5Ow0KCUdlb21EYXRhID0gKGR4VHJpTGlzdCopZEdlb21HZXRD
bGFzc0RhdGEoR2VvbWV0cnkpOw0KDQoJbWVtc2V0KEJveENvbnRhY3RzLCAwLCBzaXplb2YoQm94
Q29udGFjdHMpKTsNCn0NCg0KZGNUcmlMaXN0Q29sbGlkZXI6On5kY1RyaUxpc3RDb2xsaWRlcigp
ew0KCS8vDQp9DQoNCnZvaWQgZGNUcmlMaXN0Q29sbGlkZXI6OkJ1aWxkKGludCBWZXJ0ZXhDb3Vu
dCwgaW50IEluZGV4Q291bnQpew0KCU9wY29kZTo6T1BDT0RFQ1JFQVRFIFRyZWVCdWlsZGVyOw0K
CVRyZWVCdWlsZGVyLk5iVHJpcyA9IEluZGV4Q291bnQgLyAzOw0KCVRyZWVCdWlsZGVyLk5iVmVy
dHMJPSBWZXJ0ZXhDb3VudDsNCglUcmVlQnVpbGRlci5UcmlzID0gKHVuc2lnbmVkIGludCopSW5k
aWNlczsNCglUcmVlQnVpbGRlci5WZXJ0cyA9IChPcGNvZGU6OlBvaW50KilWZXJ0aWNlczsNCglU
cmVlQnVpbGRlci5SdWxlcyA9IE9wY29kZTo6U1BMSVRfQ09NUExFVEUgfCBPcGNvZGU6OlNQTElU
X1NQTEFUVEVSUE9JTlRTOw0KCVRyZWVCdWlsZGVyLk5vTGVhZiA9IHRydWU7DQoJVHJlZUJ1aWxk
ZXIuUXVhbnRpemVkID0gZmFsc2U7DQoJVHJlZUJ1aWxkZXIuS2VlcE9yaWdpbmFsID0gZmFsc2U7
DQoJQlZUcmVlLkJ1aWxkKFRyZWVCdWlsZGVyKTsNCn0NCg0KaW50IGRDb2xsaWRlQlAgKGNvbnN0
IGR4R2VvbSogbzEsIGNvbnN0IGR4R2VvbSogbzIsIGludCBmbGFncywgZENvbnRhY3RHZW9tICpj
b250YWN0LCBpbnQgc2tpcCk7CS8vIE9ERSBpbnRlcm5hbCBmdW5jdGlvbg0KDQovLyNkZWZpbmUg
Q09OVEFDVChDb250YWN0cywgU3RyaWRlKSAoKGRDb250YWN0R2VvbSopICgoKGNoYXIqKVB0cikg
KyAoU3RyaWRlKSkpDQppbmxpbmUgZENvbnRhY3RHZW9tKiBDT05UQUNUKGludCBGbGFncywgZENv
bnRhY3RHZW9tKiBDb250YWN0cywgaW50IEluZGV4LCBpbnQgU3RyaWRlKQ0Kew0KICBBU1NFUlQo
SW5kZXggPj0gMCAmJiBJbmRleCA8IChGbGFncyAmIDB4MGZmZmYpKTsNCiAgcmV0dXJuICgoZENv
bnRhY3RHZW9tKikgKCgoY2hhciopQ29udGFjdHMpICsgKEluZGV4ICogU3RyaWRlKSkpOw0KfQ0K
DQppbnQgZGNUcmlMaXN0Q29sbGlkZXI6OkNvbGxpZGVCb3goZHhHZW9tKiBCb3gsIGludCBGbGFn
cywgZENvbnRhY3RHZW9tKiBDb250YWN0cywgaW50IFN0cmlkZSl7DQoJZGNPQkJUcmVlQ29sbGlk
ZXImIENvbGxpZGVyID0gT0JCQ29sbGlkZXI7DQoNCgkvKiBHZXQgYm94ICovDQoJY29uc3QgZGNW
ZWN0b3IzJiBCb3hDZW50ZXIgPSAqKGRjVmVjdG9yMyopZEdlb21HZXRQb3NpdGlvbihCb3gpOw0K
DQoJZFZlY3RvcjMgQm94U2lkZXM7DQoJZEdlb21Cb3hHZXRMZW5ndGhzKEJveCwgQm94U2lkZXMp
Ow0KDQoJY29uc3QgZGNWZWN0b3IzIEJveEV4dGVudHMoQm94U2lkZXNbMF0gLyAyLjBmLCBCb3hT
aWRlc1sxXSAvIDIuMGYsIEJveFNpZGVzWzJdIC8gMi4wZik7DQoNCgljb25zdCBkUmVhbCogQm94
Um90YXRpb24gPSBkR2VvbUdldFJvdGF0aW9uKEJveCk7DQoNCgkvKiBNYWtlIE9CQiAqLw0KCU9w
Y29kZTo6TWF0cml4NHg0IEJveE1hdHJpeDsNCglCb3hNYXRyaXgubVswXVswXSA9IEJveFJvdGF0
aW9uWzBdOw0KCUJveE1hdHJpeC5tWzFdWzBdID0gQm94Um90YXRpb25bMV07DQoJQm94TWF0cml4
Lm1bMl1bMF0gPSBCb3hSb3RhdGlvblsyXTsNCg0KCUJveE1hdHJpeC5tWzBdWzFdID0gQm94Um90
YXRpb25bNF07DQoJQm94TWF0cml4Lm1bMV1bMV0gPSBCb3hSb3RhdGlvbls1XTsNCglCb3hNYXRy
aXgubVsyXVsxXSA9IEJveFJvdGF0aW9uWzZdOw0KDQoJQm94TWF0cml4Lm1bMF1bMl0gPSBCb3hS
b3RhdGlvbls4XTsNCglCb3hNYXRyaXgubVsxXVsyXSA9IEJveFJvdGF0aW9uWzldOw0KCUJveE1h
dHJpeC5tWzJdWzJdID0gQm94Um90YXRpb25bMTBdOw0KDQoJQm94TWF0cml4Lm1bM11bMF0gPSBC
b3hDZW50ZXJbMF07DQoJQm94TWF0cml4Lm1bM11bMV0gPSBCb3hDZW50ZXJbMV07DQoJQm94TWF0
cml4Lm1bM11bMl0gPSBCb3hDZW50ZXJbMl07DQoNCgkvKiBJbnRlcnNlY3QgKi8NCglDb2xsaWRl
ci5Db2xsaWRlKChjb25zdCBPcGNvZGU6OkFBQkJOb0xlYWZUcmVlKilCVlRyZWUuR2V0VHJlZSgp
LA0KICAgIChPcGNvZGU6OlBvaW50JilCb3hFeHRlbnRzLCAoT3Bjb2RlOjpNYXRyaXg0eDQmKUJv
eE1hdHJpeCk7DQoNCgkvKiBSZXRyaWV2ZSBkYXRhICovDQoJaW50IFRyaWFuZ2xlSURDb3VudCA9
IENvbGxpZGVyLkNvbnRhY3RzLnNpemUoKTsNCg0KCWlmIChUcmlhbmdsZUlEQ291bnQgIT0gMCl7
DQoJCWRBcnJheTxpbnQ+IFRyaWFuZ2xlSURzID0gQ29sbGlkZXIuQ29udGFjdHM7DQoNCgkJQ2Fs
bGJhY2soQm94LCBUcmlhbmdsZUlEcyk7DQoJCQ0KCQkvKiBHZW5lcmF0ZSBkYXRhICovDQoJCWZv
ciAoaW50IGkgPSAwOyBpIDwgVHJpYW5nbGVJRENvdW50OyBpKyspew0KCQkJY29uc3QgaW50JiBU
cmlJbmRleCA9IFRyaWFuZ2xlSURzW2ldOw0KDQoJCQlpZiAoIVZhbGlkKEJveCwgVHJpSW5kZXgp
KSBjb250aW51ZTsNCg0KCQkJLyogQ3JlYXRlIGRhdGEgKi8NCgkJCUNvbGxpc2lvblRyaWFuZ2xl
IENvbFRyaTsNCiAgICAgIG1lbXNldCgmQ29sVHJpLCAwLCBzaXplb2YoQ29sVHJpKSk7DQoJCQlm
b3IgKGludCBqID0gMDsgaiA8IDM7IGorKyl7DQoJCQkJQ29sVHJpLlZlcnRpY2VzW2pdID0gJlZl
cnRpY2VzW0luZGljZXNbVHJpSW5kZXggKiAzICsgal1dOw0KCQkJfQ0KCQkJQ29sVHJpLlBsYW5l
ID0gZGNQbGFuZSgqQ29sVHJpLlZlcnRpY2VzWzBdLCAqQ29sVHJpLlZlcnRpY2VzWzFdLCAqQ29s
VHJpLlZlcnRpY2VzWzJdKTsNCg0KCQkJaWYgKENvbFRyaS5QbGFuZS5Db250YWlucyhCb3hDZW50
ZXIpKXsNCgkJCQlmb3IgKGludCBqID0gMDsgaiA8IDM7IGorKyl7DQoJCQkJCWNvbnN0IGRjVmVj
dG9yMyYgdjAgPSAqQ29sVHJpLlZlcnRpY2VzW2pdOw0KCQkJCQljb25zdCBkY1ZlY3RvcjMmIHYx
ID0gKkNvbFRyaS5WZXJ0aWNlc1soaiArIDEpICUgM107DQoJCQkJCUNvbFRyaS5FZGdlc1tqXSA9
IGRjUGxhbmUodjAsIHYxLCB2MSAtIENvbFRyaS5QbGFuZS5Ob3JtYWwpOw0KCQkJCX0NCgkJCQlm
bG9hdCBEaXN0U3E7DQogICAgICAgIERpc3RTcSA9IENvbFRyaS5QbGFuZS5Ob3JtYWwuRG90UHJv
ZHVjdChCb3hDZW50ZXIgLSAqQ29sVHJpLlZlcnRpY2VzWzBdKTsNCgkJCQlDb2xUcmkuQ2xvc2Vz
dFBvaW50ID0gQm94Q2VudGVyIC0gKENvbFRyaS5QbGFuZS5Ob3JtYWwgKiBDb2xUcmkuRGlzdFNx
KTsNCgkJCQlDb2xUcmkuRGlzdFNxID0gZmFic2YoQ29sVHJpLkRpc3RTcSk7DQoJCQkJDQoJCQkJ
LyogSW5zZXJ0IGRhdGEgKi8NCgkJCQlpbnQgSW5kZXg7DQoJCQkJZm9yIChJbmRleCA9IDA7IElu
ZGV4IDwgQ29sbGlzaW9uVHJpYW5nbGVzLnNpemUoKTsgSW5kZXgrKyl7DQoJCQkJCWlmIChDb2xU
cmkuRGlzdFNxIDwgQ29sbGlzaW9uVHJpYW5nbGVzW0luZGV4XS5EaXN0U3Epew0KCQkJCQkJQ29s
bGlzaW9uVHJpYW5nbGVzLmluc2VydChJbmRleCwgQ29sVHJpKTsNCgkJCQkJCWJyZWFrOw0KCQkJ
CQl9DQoJCQkJfQ0KCQkJCWlmIChJbmRleCA9PSBDb2xsaXNpb25UcmlhbmdsZXMuc2l6ZSgpKXsN
CgkJCQkJQ29sbGlzaW9uVHJpYW5nbGVzLnB1c2goQ29sVHJpKTsNCgkJCQl9DQoJCQl9DQoJCX0N
Cg0KCQlpZiAoQ29sbGlzaW9uVHJpYW5nbGVzLnNpemUoKSAhPSAwKXsNCgkJCS8qIEdlbmVyYXRp
bmcgY29udGFjdHMgKi8NCgkJCWludCBPdXRUcmlDb3VudCA9IDA7DQoJCQlmb3IgKGludCBpID0g
MDsgaSA8IENvbGxpc2lvblRyaWFuZ2xlcy5zaXplKCk7IGkrKyl7DQoJCQkJZGNQbGFuZSYgVHJp
UGxhbmUgPSAqKGRjUGxhbmUqKWRHZW9tR2V0Q2xhc3NEYXRhKEdlb21ldHJ5KTsNCgkJCQlUcmlQ
bGFuZSA9IENvbGxpc2lvblRyaWFuZ2xlc1tpXS5QbGFuZTsNCgkJCQkNCgkJCQlpbnQgQ29udGFj
dENvdW50ID0gZENvbGxpZGVCUChCb3gsIEdlb21ldHJ5LCAzLCBCb3hDb250YWN0cywgc2l6ZW9m
KGRDb250YWN0R2VvbSkpOw0KDQoJCQkJZm9yIChpbnQgaiA9IDA7IGogPCBDb250YWN0Q291bnQ7
IGorKyl7DQoJCQkJCWRjVmVjdG9yMyYgUG9zID0gKGRjVmVjdG9yMyYpQm94Q29udGFjdHNbal0u
cG9zOw0KCQkJCQlkY1ZlY3RvcjMgTm9ybWFsID0gKChkY1ZlY3RvcjMmKUJveENvbnRhY3RzW2pd
Lm5vcm1hbCkgKiAtMTsNCgkJCQkJZFJlYWwmIERlcHRoID0gQm94Q29udGFjdHNbal0uZGVwdGg7
DQoJCQkJCQ0KCQkJCQlmb3IgKGludCBrID0gMDsgayA8IDM7IGsrKyl7DQoJCQkJCQlkY1BsYW5l
JiBFZGdlID0gQ29sbGlzaW9uVHJpYW5nbGVzW2ldLkVkZ2VzW2tdOw0KCQkJCQkJY29uc3QgZmxv
YXQgUG9pbnREZXB0aCA9IEVkZ2UuRGlzdGFuY2UgLSBQb3MuRG90UHJvZHVjdChFZGdlLk5vcm1h
bCk7DQoJCQkJCQlpZiAoUG9pbnREZXB0aCA+IDAuMGYpew0KCQkJCQkJCVBvcyArPSBFZGdlLk5v
cm1hbCAqIFBvaW50RGVwdGg7DQoJCQkJCQkJRGVwdGggPSAwLjBmOw0KCQkJCQkJfQ0KCQkJCQl9
DQoJCQkJCWludCBJbmRleDsNCgkJCQkJZm9yIChJbmRleCA9IDA7IEluZGV4IDwgT3V0VHJpQ291
bnQ7IEluZGV4Kyspew0KCQkJCQkJZENvbnRhY3RHZW9tKiBSZWYgPSBDT05UQUNUKEZsYWdzLCBD
b250YWN0cywgSW5kZXgsIFN0cmlkZSk7DQoJCQkJCQlmbG9hdCBEaXN0U3EgPSAoKGRjVmVjdG9y
MyYpUmVmLT5wb3MgLSBQb3MpLk1hZ25pdHVkZVNxKCk7DQoJCQkJCQlpZiAoRGlzdFNxIDwgMC4x
Zil7DQoJCQkJCQkJZGNWZWN0b3IzJiBSZWZOb3JtYWwgPSAoZGNWZWN0b3IzJilSZWYtPm5vcm1h
bDsNCgkJCQkJCQlSZWZOb3JtYWwgKz0gTm9ybWFsOw0KCQkJCQkJCVJlZk5vcm1hbC5Ob3JtYWxp
emUoKTsNCgkJCQkJCX0NCgkJCQkJfQ0KCQkJCQlpZiAoSW5kZXggPT0gT3V0VHJpQ291bnQpew0K
CQkJCQkJZENvbnRhY3RHZW9tJiBPdXRDb250YWN0ID0gKkNPTlRBQ1QoRmxhZ3MsIENvbnRhY3Rz
LCBPdXRUcmlDb3VudCwgU3RyaWRlKTsNCgkJCQkJCU91dENvbnRhY3QucG9zWzBdID0gUG9zLng7
DQoJCQkJCQlPdXRDb250YWN0LnBvc1sxXSA9IFBvcy55Ow0KCQkJCQkJT3V0Q29udGFjdC5wb3Nb
Ml0gPSBQb3MuejsNCgkJCQkJCU91dENvbnRhY3Qubm9ybWFsWzBdID0gTm9ybWFsLng7DQoJCQkJ
CQlPdXRDb250YWN0Lm5vcm1hbFsxXSA9IE5vcm1hbC55Ow0KCQkJCQkJT3V0Q29udGFjdC5ub3Jt
YWxbMl0gPSBOb3JtYWwuejsNCgkJCQkJCU91dENvbnRhY3QuZGVwdGggPSBEZXB0aDsNCgkJCQkJ
CU91dENvbnRhY3QuZzEgPSBCb3hDb250YWN0c1tqXS5nMjsNCgkJCQkJCU91dENvbnRhY3QuZzIg
PSBCb3hDb250YWN0c1tqXS5nMTsNCiNpZmRlZiBHRU5FUkFURUJPRElFUw0KCQkJCQkJT3V0Q29u
dGFjdC5iMSA9IEJveENvbnRhY3RzW2pdLmIyOw0KCQkJCQkJT3V0Q29udGFjdC5iMiA9IEJveENv
bnRhY3RzW2pdLmIxOw0KI2VuZGlmCS8vR0VORVJBVEVCT0RJRVMNCg0KCQkJCQkJT3V0VHJpQ291
bnQrKzsNCgkJCQkJfQ0KCQkJCX0NCgkJCX0NCgkJCUNvbGxpc2lvblRyaWFuZ2xlcy5zZXRTaXpl
KDApOw0KDQoJCQlyZXR1cm4gT3V0VHJpQ291bnQ7DQoJCX0NCgkJZWxzZSByZXR1cm4gMDsNCgl9
DQoJZWxzZSByZXR1cm4gMDsNCn0NCg0KaW50IGRjVHJpTGlzdENvbGxpZGVyOjpDb2xsaWRlUmF5
KGR4R2VvbSogUmF5R2VvbSwgaW50IEZsYWdzLCBkQ29udGFjdEdlb20qIENvbnRhY3RzLCBpbnQg
U3RyaWRlKXsNCiAgZGNBQUJCVHJlZUNvbGxpZGVyJiBDb2xsaWRlciA9IEFBQkJDb2xsaWRlcjsN
Cg0KICAvKiBHZXQgcmF5ICovDQogIGRWZWN0b3IzIG8sIGQ7DQogIGRHZW9tUmF5R2V0KFJheUdl
b20sIG8sIGQpOw0KICBkY1ZlY3RvcjMgUmF5T3JpZ2luKG8pLCBSYXlEaXJlY3Rpb24oZCk7DQog
IGRSZWFsIFJheUxlbmd0aCA9IGRHZW9tUmF5R2V0TGVuZ3RoKFJheUdlb20pOw0KICBkUmVhbCBS
YXlMZW5ndGgyID0gUmF5TGVuZ3RoLzI7DQogIGRjVmVjdG9yMyBSYXlDZW50ZXIgPSBSYXlPcmln
aW4gKyBSYXlEaXJlY3Rpb24gKiBSYXlMZW5ndGgyOw0KDQogIC8qIE1ha2UgQUFCQiAqLw0KICBP
cGNvZGU6OkNvbGxpc2lvbkFBQkIgQm94Ow0KICBCb3gubUNlbnRlciA9IChPcGNvZGU6OlBvaW50
JilSYXlDZW50ZXI7DQogIEJveC5tRXh0ZW50cy54ID0gUmF5TGVuZ3RoMjsNCiAgQm94Lm1FeHRl
bnRzLnkgPSBSYXlMZW5ndGgyOw0KICBCb3gubUV4dGVudHMueiA9IFJheUxlbmd0aDI7DQoNCiAg
LyogSW50ZXJzZWN0ICovDQogIENvbGxpZGVyLkNvbGxpZGUoKE9wY29kZTo6QUFCQk5vTGVhZlRy
ZWUqKUJWVHJlZS5HZXRUcmVlKCksIEJveCk7DQoNCiAgLyogUmV0cmlldmUgZGF0YSAqLw0KICBp
bnQgVHJpYW5nbGVJRENvdW50ID0gQ29sbGlkZXIuQ29udGFjdHMuc2l6ZSgpOw0KDQogIGlmIChU
cmlhbmdsZUlEQ291bnQgIT0gMCl7DQogICAgZEFycmF5PGludD4mIFRyaWFuZ2xlSURzID0gQ29s
bGlkZXIuQ29udGFjdHM7DQoNCiAgICBDYWxsYmFjayhSYXlHZW9tLCBUcmlhbmdsZUlEcyk7DQoN
CiAgICAvKiBDcmVhdGluZyBtaW5pbXVtIGNvbnRhY3RzICovDQogICAgaW50IE91dFRyaUNvdW50
ID0gMDsNCiAgICBmb3IgKGludCBpID0gMDsgaSA8IFRyaWFuZ2xlSURDb3VudDsgaSsrKXsNCiAg
ICAgIGNvbnN0IGludCYgVHJpSW5kZXggPSBUcmlhbmdsZUlEc1tpXTsNCg0KICAgICAgaWYgKCFW
YWxpZChSYXlHZW9tLCBUcmlJbmRleCkpIGNvbnRpbnVlOw0KDQogICAgICBjb25zdCBkY1ZlY3Rv
cjMmIHYwID0gVmVydGljZXNbSW5kaWNlc1tUcmlJbmRleCAqIDMgKyAwXV07DQogICAgICBjb25z
dCBkY1ZlY3RvcjMmIHYxID0gVmVydGljZXNbSW5kaWNlc1tUcmlJbmRleCAqIDMgKyAxXV07DQog
ICAgICBjb25zdCBkY1ZlY3RvcjMmIHYyID0gVmVydGljZXNbSW5kaWNlc1tUcmlJbmRleCAqIDMg
KyAyXV07DQoNCiAgICAgIGRjUGxhbmUgVHJpUGxhbmUodjAsIHYxLCB2Mik7DQogICAgICBjb25z
dCBkY1ZlY3RvcjMmIENvbnRhY3ROb3JtYWwgPSBUcmlQbGFuZS5Ob3JtYWw7DQoNCiAgICAgIGRS
ZWFsIERlbm9tID0gQ29udGFjdE5vcm1hbC5Eb3RQcm9kdWN0KFJheURpcmVjdGlvbik7DQogICAg
ICBpZiAoZEZhYnMoRGVub20pIDwgMC4wMDAwMWYpew0KICAgICAgICBjb250aW51ZTsJLy8gUmF5
IG5ldmVyIGhpdHMNCiAgICAgIH0NCg0KICAgICAgZFJlYWwgQ29udGFjdERlcHRoID0gQ29udGFj
dE5vcm1hbC5Eb3RQcm9kdWN0KFJheU9yaWdpbik7DQogICAgICBDb250YWN0RGVwdGggPSAoVHJp
UGxhbmUuRGlzdGFuY2UgLSBDb250YWN0RGVwdGgpIC8gRGVub207DQogICAgICBpZiAoQ29udGFj
dERlcHRoIDwgMCB8fCBDb250YWN0RGVwdGggPiBSYXlMZW5ndGgpew0KICAgICAgICBjb250aW51
ZTsJLy8gUmF5IGhpdHMgYnV0IG5vdCB3aXRoaW4gYm91bmRhcmllcw0KICAgICAgfQ0KDQogICAg
ICBjb25zdCBkY1ZlY3RvcjMgQ29udGFjdFBvcyA9IFJheU9yaWdpbiArIFJheURpcmVjdGlvbiAq
IENvbnRhY3REZXB0aDsNCg0KICAgICAgLy8gSW5zaWRlIHRyaWFuZ2xlPw0KICAgICAgaW50IElu
ZGV4Ow0KICAgICAgZm9yIChJbmRleCA9IDA7IEluZGV4IDwgMzsgSW5kZXgrKyl7DQogICAgICAg
IGNvbnN0IGRjVmVjdG9yMyYgdjAgPSBWZXJ0aWNlc1tJbmRpY2VzW1RyaUluZGV4ICogMyArIElu
ZGV4XV07DQogICAgICAgIGNvbnN0IGRjVmVjdG9yMyYgdjEgPSBWZXJ0aWNlc1tJbmRpY2VzW1Ry
aUluZGV4ICogMyArIChJbmRleCArIDEpICUgM11dOw0KICAgICAgICBkY1BsYW5lIFBsYW5lKHYw
LCB2MSwgdjEgLSBUcmlQbGFuZS5Ob3JtYWwpOw0KDQogICAgICAgIGlmICghUGxhbmUuQ29udGFp
bnMoQ29udGFjdFBvcykpew0KICAgICAgICAgIGJyZWFrOw0KICAgICAgICB9DQogICAgICB9DQog
ICAgICBpZiAoSW5kZXggPT0gMyl7DQogICAgICAgIGRDb250YWN0R2VvbSYgT3V0Q29udGFjdCA9
ICpDb250YWN0czsNCiAgICAgICAgaWYgKE91dFRyaUNvdW50ID09IDAgfHwgQ29udGFjdERlcHRo
IDwgT3V0Q29udGFjdC5kZXB0aCkgew0KICAgICAgICAgICgoZGNWZWN0b3IzJilPdXRDb250YWN0
LnBvcykgPSBDb250YWN0UG9zOw0KICAgICAgICAgICgoZGNWZWN0b3IzJilPdXRDb250YWN0Lm5v
cm1hbCkgPSBDb250YWN0Tm9ybWFsOw0KICAgICAgICAgIE91dENvbnRhY3QuZGVwdGggPSBDb250
YWN0RGVwdGg7DQogICAgICAgICAgT3V0VHJpQ291bnQgPSAxOw0KICAgICAgICB9DQogICAgICB9
DQogICAgfQ0KDQogICAgaWYgKE91dFRyaUNvdW50ICE9IDApew0KICAgICAgZENvbnRhY3RHZW9t
JiBPdXRDb250YWN0ID0gKkNvbnRhY3RzOw0KICAgICAgT3V0Q29udGFjdC5nMSA9IFJheUdlb207
DQogICAgICBPdXRDb250YWN0LmcyID0gR2VvbWV0cnk7DQojaWZkZWYgR0VORVJBVEVCT0RJRVMN
CiAgICAgIE91dENvbnRhY3QuYjEgPSBkR2VvbUdldEJvZHkoUmF5R2VvbSk7DQogICAgICBPdXRD
b250YWN0LmIyID0gZEdlb21HZXRCb2R5KEdlb21ldHJ5KTsNCiNlbmRpZgkvL0dFTkVSQVRFQk9E
SUVTDQogICAgICByZXR1cm4gMTsNCiAgICB9DQogICAgZWxzZSByZXR1cm4gMDsNCiAgfQ0KICBl
bHNlIHJldHVybiAwOw0KfQ0KDQppbnQgZGNUcmlMaXN0Q29sbGlkZXI6OkNvbGxpZGVTcGhlcmUo
ZHhHZW9tKiBTcGhlcmUsIGludCBGbGFncywgZENvbnRhY3RHZW9tKiBDb250YWN0cywgaW50IFN0
cmlkZSl7DQoJZGNBQUJCVHJlZUNvbGxpZGVyJiBDb2xsaWRlciA9IEFBQkJDb2xsaWRlcjsNCg0K
CS8qIEdldCBzcGhlcmUgKi8NCgljb25zdCBkY1ZlY3RvcjMgU3BoZXJlQ2VudGVyKGRHZW9tR2V0
UG9zaXRpb24oU3BoZXJlKSk7DQoJY29uc3QgZmxvYXQgU3BoZXJlUmFkaXVzID0gZEdlb21TcGhl
cmVHZXRSYWRpdXMoU3BoZXJlKTsNCg0KCS8qIE1ha2UgQUFCQiAqLw0KCU9wY29kZTo6Q29sbGlz
aW9uQUFCQiBCb3g7DQoJQm94Lm1DZW50ZXIgPSAoT3Bjb2RlOjpQb2ludCYpU3BoZXJlQ2VudGVy
Ow0KCUJveC5tRXh0ZW50cy54ID0gU3BoZXJlUmFkaXVzOw0KCUJveC5tRXh0ZW50cy55ID0gU3Bo
ZXJlUmFkaXVzOw0KCUJveC5tRXh0ZW50cy56ID0gU3BoZXJlUmFkaXVzOw0KDQoJLyogSW50ZXJz
ZWN0ICovDQoJQ29sbGlkZXIuQ29sbGlkZSgoT3Bjb2RlOjpBQUJCTm9MZWFmVHJlZSopQlZUcmVl
LkdldFRyZWUoKSwgQm94KTsNCgkNCgkvKiBSZXRyaWV2ZSBkYXRhICovDQoJaW50IFRyaWFuZ2xl
SURDb3VudCA9IENvbGxpZGVyLkNvbnRhY3RzLnNpemUoKTsNCgkNCglpZiAoVHJpYW5nbGVJRENv
dW50ICE9IDApew0KCQlkQXJyYXk8aW50PiYgVHJpYW5nbGVJRHMgPSBDb2xsaWRlci5Db250YWN0
czsNCg0KCQlDYWxsYmFjayhTcGhlcmUsIFRyaWFuZ2xlSURzKTsNCg0KCQkvKiBDcmVhdGluZyBt
aW5pbXVtIGNvbnRhY3RzICovDQoJCWludCBPdXRUcmlDb3VudCA9IDA7DQoJCWZvciAoaW50IGkg
PSAwOyBpIDwgVHJpYW5nbGVJRENvdW50OyBpKyspew0KCQkJY29uc3QgaW50JiBUcmlJbmRleCA9
IFRyaWFuZ2xlSURzW2ldOw0KDQoJCQlpZiAoIVZhbGlkKFNwaGVyZSwgVHJpSW5kZXgpKSBjb250
aW51ZTsNCg0KCQkJY29uc3QgZGNWZWN0b3IzJiB2MCA9IFZlcnRpY2VzW0luZGljZXNbVHJpSW5k
ZXggKiAzICsgMF1dOw0KCQkJY29uc3QgZGNWZWN0b3IzJiB2MSA9IFZlcnRpY2VzW0luZGljZXNb
VHJpSW5kZXggKiAzICsgMV1dOw0KCQkJY29uc3QgZGNWZWN0b3IzJiB2MiA9IFZlcnRpY2VzW0lu
ZGljZXNbVHJpSW5kZXggKiAzICsgMl1dOw0KDQoJCQlkY1BsYW5lIFRyaVBsYW5lKHYwLCB2MSwg
djIpOw0KDQoJCQlpZiAoIVRyaVBsYW5lLkNvbnRhaW5zKFNwaGVyZUNlbnRlcikpew0KCQkJCWNv
bnRpbnVlOw0KCQkJfQ0KDQoJCQljb25zdCBkY1ZlY3RvcjMmIENvbnRhY3ROb3JtYWwgPSBUcmlQ
bGFuZS5Ob3JtYWw7DQoJCQljb25zdCBkY1ZlY3RvcjMgQ29udGFjdFBvcyA9IFNwaGVyZUNlbnRl
ciAtIENvbnRhY3ROb3JtYWwgKiBTcGhlcmVSYWRpdXM7DQoJCQljb25zdCBmbG9hdCBDb250YWN0
RGVwdGggPSBUcmlQbGFuZS5EaXN0YW5jZSAtIFNwaGVyZUNlbnRlci5Eb3RQcm9kdWN0KFRyaVBs
YW5lLk5vcm1hbCkgKyBTcGhlcmVSYWRpdXM7DQoNCgkJCWlmIChDb250YWN0RGVwdGggPj0gMCl7
DQoJCQkJaW50IEluZGV4Ow0KCQkJCWZvciAoSW5kZXggPSAwOyBJbmRleCA8IDM7IEluZGV4Kysp
ew0KCQkJCQljb25zdCBkY1ZlY3RvcjMmIHYwID0gVmVydGljZXNbSW5kaWNlc1tUcmlJbmRleCAq
IDMgKyBJbmRleF1dOw0KCQkJCQljb25zdCBkY1ZlY3RvcjMmIHYxID0gVmVydGljZXNbSW5kaWNl
c1tUcmlJbmRleCAqIDMgKyAoSW5kZXggKyAxKSAlIDNdXTsNCgkJCQkJZGNQbGFuZSBQbGFuZSh2
MCwgdjEsIHYxIC0gVHJpUGxhbmUuTm9ybWFsKTsNCg0KCQkJCQlpZiAoIVBsYW5lLkNvbnRhaW5z
KENvbnRhY3RQb3MpKXsNCgkJCQkJCWJyZWFrOw0KCQkJCQl9DQoJCQkJfQ0KCQkJCWlmIChJbmRl
eCA9PSAzKXsNCgkJCQkJZm9yIChJbmRleCA9IDA7IEluZGV4IDwgT3V0VHJpQ291bnQ7IEluZGV4
Kyspew0KCQkJCQkJZENvbnRhY3RHZW9tKiBSZWZDb250YWN0ID0gQ09OVEFDVChGbGFncywgQ29u
dGFjdHMsIEluZGV4LCBTdHJpZGUpOw0KCQkJCQkJY29uc3QgZGNWZWN0b3IzJiBSZWZOb3JtYWwg
PSAoZGNWZWN0b3IzJilSZWZDb250YWN0LT5ub3JtYWw7DQoNCgkJCQkJCWlmIChUcmlQbGFuZS5O
b3JtYWwuRG90UHJvZHVjdChSZWZOb3JtYWwpID4gMC45Zil7CS8vIENvcGxhbml0YXJ5IHRlc3QN
CgkJCQkJCQlSZWZDb250YWN0LT5kZXB0aCA9IGRjTUFYKChmbG9hdClSZWZDb250YWN0LT5kZXB0
aCwgQ29udGFjdERlcHRoKTsNCgkJCQkJCQlicmVhazsNCgkJCQkJCX0NCgkJCQkJfQ0KDQoJCQkJ
CWlmIChJbmRleCA9PSBPdXRUcmlDb3VudCl7DQoJCQkJCQlkQ29udGFjdEdlb20qIENvbnRhY3Qg
PSBDT05UQUNUKEZsYWdzLCBDb250YWN0cywgT3V0VHJpQ291bnQsIFN0cmlkZSk7DQoJCQkJCQko
KGRjVmVjdG9yMyYpQ29udGFjdC0+bm9ybWFsKSA9IFRyaVBsYW5lLk5vcm1hbDsNCgkJCQkJCUNv
bnRhY3QtPmRlcHRoID0gQ29udGFjdERlcHRoOw0KCQkJCQkJT3V0VHJpQ291bnQrKzsNCgkJCQkJ
fQ0KCQkJCX0NCgkJCX0NCgkJfQ0KDQoJCWlmIChPdXRUcmlDb3VudCAhPSAwKXsNCgkJCWRjVmVj
dG9yMyBPdXROb3JtYWwoMCwgMCwgMCk7DQoJCQ0KCQkJLyogQ29tYmluaW5nIGNvbnRhY3RzICov
DQoJCQlmb3IgKGludCBpID0gMDsgaSA8IE91dFRyaUNvdW50OyBpKyspew0KCQkJCWRDb250YWN0
R2VvbSogQ29udGFjdCA9IENPTlRBQ1QoRmxhZ3MsIENvbnRhY3RzLCBpLCBTdHJpZGUpOw0KDQoJ
CQkJT3V0Tm9ybWFsICs9ICgoZGNWZWN0b3IzJilDb250YWN0LT5ub3JtYWwpICogQ29udGFjdC0+
ZGVwdGg7DQoJCQl9DQoNCgkJCWNvbnN0IGZsb2F0IERlcHRoU3EgPSBPdXROb3JtYWwuTWFnbml0
dWRlU3EoKTsNCg0KCQkJLyogR2VuZXJhdGluZyBmaW5hbCBjb250YWN0ICovDQoJCQlpZiAoRGVw
dGhTcSA+IDAuMGYpew0KCQkJCWNvbnN0IGZsb2F0IERlcHRoID0gc3FydGYoRGVwdGhTcSk7DQoN
CgkJCQlPdXROb3JtYWwgLz0gRGVwdGg7CS8vIE5vcm1hbGl6aW5nDQoNCgkJCQlkQ29udGFjdEdl
b20mIE91dENvbnRhY3QgPSAqQ29udGFjdHM7DQoJCQkJKChkY1ZlY3RvcjMmKU91dENvbnRhY3Qu
cG9zKSA9IFNwaGVyZUNlbnRlciAtIE91dE5vcm1hbCAqIFNwaGVyZVJhZGl1czsNCgkJCQkoKGRj
VmVjdG9yMyYpT3V0Q29udGFjdC5ub3JtYWwpID0gT3V0Tm9ybWFsOw0KCQkJCU91dENvbnRhY3Qu
ZGVwdGggPSBEZXB0aDsNCg0KCQkJCU91dENvbnRhY3QuZzEgPSBTcGhlcmU7DQoJCQkJT3V0Q29u
dGFjdC5nMiA9IEdlb21ldHJ5Ow0KI2lmZGVmIEdFTkVSQVRFQk9ESUVTDQoJCQkJT3V0Q29udGFj
dC5iMSA9IGRHZW9tR2V0Qm9keShTcGhlcmUpOw0KCQkJCU91dENvbnRhY3QuYjIgPSBkR2VvbUdl
dEJvZHkoR2VvbWV0cnkpOw0KI2VuZGlmCS8vR0VORVJBVEVCT0RJRVMNCg0KCQkJCXJldHVybiAx
Ow0KCQkJfQ0KCQkJZWxzZSByZXR1cm4gMDsNCgkJfQ0KCQllbHNlIHJldHVybiAwOw0KCX0NCgll
bHNlIHJldHVybiAwOw0KfQ0KDQpib29sIGRjVHJpTGlzdENvbGxpZGVyOjpHZW5lcmF0ZVRDKGR4
R2VvbSogT2JqZWN0LCBjb25zdCBPcGNvZGU6OkNvbGxpc2lvbkFBQkImIEJveCl7DQoJVENEYXRh
LnNldFNpemUoMCk7DQoNCglBQUJCQ29sbGlkZXIuVENEYXRhID0gJlRDRGF0YTsNCglBQUJCQ29s
bGlkZXIuR2VuZXJhdGVUQygoT3Bjb2RlOjpBQUJCTm9MZWFmVHJlZSopQlZUcmVlLkdldFRyZWUo
KSwgQm94KTsNCg0KCWlmIChUQ0RhdGEuc2l6ZSgpICE9IDApew0KCQlPQkJDb2xsaWRlci5UQ0Rh
dGEgPSAmVENEYXRhOw0KCQlyZXR1cm4gdHJ1ZTsNCgl9DQoJZWxzZSB7DQoJCUFBQkJDb2xsaWRl
ci5UQ0RhdGEgPSBudWxsOw0KCQlyZXR1cm4gZmFsc2U7DQoJfQ0KfQ0KDQp2b2lkIGRjVHJpTGlz
dENvbGxpZGVyOjpDbGVhclRDKCl7DQoJQUFCQkNvbGxpZGVyLlRDRGF0YSA9IG51bGw7DQoJT0JC
Q29sbGlkZXIuVENEYXRhID0gbnVsbDsNCn0NCg0Kdm9pZCBkY1RyaUxpc3RDb2xsaWRlcjo6Q2Fs
bGJhY2soZHhHZW9tKiBPYmplY3QsIGRBcnJheTxpbnQ+JiBUcmlJbmRpY2VzKXsNCglpZiAoR2Vv
bURhdGEtPkFycmF5Q2FsbGJhY2sgIT0gbnVsbCl7DQoJCUdlb21EYXRhLT5BcnJheUNhbGxiYWNr
KEdlb21ldHJ5LCBPYmplY3QsIFRyaUluZGljZXMuZGF0YSgpLCBUcmlJbmRpY2VzLnNpemUoKSk7
DQoJfQ0KfQ0KDQpib29sIGRjVHJpTGlzdENvbGxpZGVyOjpWYWxpZChkeEdlb20qIE9iamVjdCwg
aW50IFRyaUluZGV4KXsNCglpZiAoR2VvbURhdGEtPkNhbGxiYWNrICE9IG51bGwpew0KCQlyZXR1
cm4gR2VvbURhdGEtPkNhbGxiYWNrKEdlb21ldHJ5LCBPYmplY3QsIFRyaUluZGV4KSAhPSAwOw0K
CX0NCgllbHNlIHJldHVybiB0cnVlOw0KfQ0K

------_=_NextPart_001_01C248CA.2E39C162--