]> git.proxmox.com Git - mirror_edk2.git/blob - AppPkg/Applications/Python/Python-2.7.10/Modules/shamodule.c
AppPkg/Applications/Python/Python-2.7.10: Initial Checkin part 2/5.
[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.10 / Modules / shamodule.c
1 /* SHA module */
2
3 /* This module provides an interface to NIST's Secure Hash Algorithm */
4
5 /* See below for information about the original code this module was
6 based upon. Additional work performed by:
7
8 Andrew Kuchling (amk@amk.ca)
9 Greg Stein (gstein@lyra.org)
10
11 Copyright (C) 2005 Gregory P. Smith (greg@krypto.org)
12 Licensed to PSF under a Contributor Agreement.
13
14 */
15
16 /* SHA objects */
17
18 #include "Python.h"
19 #include "structmember.h"
20
21
22 /* Endianness testing and definitions */
23 #define TestEndianness(variable) {int i=1; variable=PCT_BIG_ENDIAN;\
24 if (*((char*)&i)==1) variable=PCT_LITTLE_ENDIAN;}
25
26 #define PCT_LITTLE_ENDIAN 1
27 #define PCT_BIG_ENDIAN 0
28
29 /* Some useful types */
30
31 typedef unsigned char SHA_BYTE;
32
33 #if SIZEOF_INT == 4
34 typedef unsigned int SHA_INT32; /* 32-bit integer */
35 #else
36 /* not defined. compilation will die. */
37 #endif
38
39 /* The SHA block size and message digest sizes, in bytes */
40
41 #define SHA_BLOCKSIZE 64
42 #define SHA_DIGESTSIZE 20
43
44 /* The structure for storing SHS info */
45
46 typedef struct {
47 PyObject_HEAD
48 SHA_INT32 digest[5]; /* Message digest */
49 SHA_INT32 count_lo, count_hi; /* 64-bit bit count */
50 SHA_BYTE data[SHA_BLOCKSIZE]; /* SHA data buffer */
51 int Endianness;
52 int local; /* unprocessed amount in data */
53 } SHAobject;
54
55 /* When run on a little-endian CPU we need to perform byte reversal on an
56 array of longwords. */
57
58 static void longReverse(SHA_INT32 *buffer, int byteCount, int Endianness)
59 {
60 SHA_INT32 value;
61
62 if ( Endianness == PCT_BIG_ENDIAN )
63 return;
64
65 byteCount /= sizeof(*buffer);
66 while (byteCount--) {
67 value = *buffer;
68 value = ( ( value & 0xFF00FF00L ) >> 8 ) | \
69 ( ( value & 0x00FF00FFL ) << 8 );
70 *buffer++ = ( value << 16 ) | ( value >> 16 );
71 }
72 }
73
74 static void SHAcopy(SHAobject *src, SHAobject *dest)
75 {
76 dest->Endianness = src->Endianness;
77 dest->local = src->local;
78 dest->count_lo = src->count_lo;
79 dest->count_hi = src->count_hi;
80 memcpy(dest->digest, src->digest, sizeof(src->digest));
81 memcpy(dest->data, src->data, sizeof(src->data));
82 }
83
84
85 /* ------------------------------------------------------------------------
86 *
87 * This code for the SHA algorithm was noted as public domain. The original
88 * headers are pasted below.
89 *
90 * Several changes have been made to make it more compatible with the
91 * Python environment and desired interface.
92 *
93 */
94
95 /* NIST Secure Hash Algorithm */
96 /* heavily modified by Uwe Hollerbach <uh@alumni.caltech edu> */
97 /* from Peter C. Gutmann's implementation as found in */
98 /* Applied Cryptography by Bruce Schneier */
99 /* Further modifications to include the "UNRAVEL" stuff, below */
100
101 /* This code is in the public domain */
102
103 /* UNRAVEL should be fastest & biggest */
104 /* UNROLL_LOOPS should be just as big, but slightly slower */
105 /* both undefined should be smallest and slowest */
106
107 #define UNRAVEL
108 /* #define UNROLL_LOOPS */
109
110 /* The SHA f()-functions. The f1 and f3 functions can be optimized to
111 save one boolean operation each - thanks to Rich Schroeppel,
112 rcs@cs.arizona.edu for discovering this */
113
114 /*#define f1(x,y,z) ((x & y) | (~x & z)) // Rounds 0-19 */
115 #define f1(x,y,z) (z ^ (x & (y ^ z))) /* Rounds 0-19 */
116 #define f2(x,y,z) (x ^ y ^ z) /* Rounds 20-39 */
117 /*#define f3(x,y,z) ((x & y) | (x & z) | (y & z)) // Rounds 40-59 */
118 #define f3(x,y,z) ((x & y) | (z & (x | y))) /* Rounds 40-59 */
119 #define f4(x,y,z) (x ^ y ^ z) /* Rounds 60-79 */
120
121 /* SHA constants */
122
123 #define CONST1 0x5a827999L /* Rounds 0-19 */
124 #define CONST2 0x6ed9eba1L /* Rounds 20-39 */
125 #define CONST3 0x8f1bbcdcL /* Rounds 40-59 */
126 #define CONST4 0xca62c1d6L /* Rounds 60-79 */
127
128 /* 32-bit rotate */
129
130 #define R32(x,n) ((x << n) | (x >> (32 - n)))
131
132 /* the generic case, for when the overall rotation is not unraveled */
133
134 #define FG(n) \
135 T = R32(A,5) + f##n(B,C,D) + E + *WP++ + CONST##n; \
136 E = D; D = C; C = R32(B,30); B = A; A = T
137
138 /* specific cases, for when the overall rotation is unraveled */
139
140 #define FA(n) \
141 T = R32(A,5) + f##n(B,C,D) + E + *WP++ + CONST##n; B = R32(B,30)
142
143 #define FB(n) \
144 E = R32(T,5) + f##n(A,B,C) + D + *WP++ + CONST##n; A = R32(A,30)
145
146 #define FC(n) \
147 D = R32(E,5) + f##n(T,A,B) + C + *WP++ + CONST##n; T = R32(T,30)
148
149 #define FD(n) \
150 C = R32(D,5) + f##n(E,T,A) + B + *WP++ + CONST##n; E = R32(E,30)
151
152 #define FE(n) \
153 B = R32(C,5) + f##n(D,E,T) + A + *WP++ + CONST##n; D = R32(D,30)
154
155 #define FT(n) \
156 A = R32(B,5) + f##n(C,D,E) + T + *WP++ + CONST##n; C = R32(C,30)
157
158 /* do SHA transformation */
159
160 static void
161 sha_transform(SHAobject *sha_info)
162 {
163 int i;
164 SHA_INT32 T, A, B, C, D, E, W[80], *WP;
165
166 memcpy(W, sha_info->data, sizeof(sha_info->data));
167 longReverse(W, (int)sizeof(sha_info->data), sha_info->Endianness);
168
169 for (i = 16; i < 80; ++i) {
170 W[i] = W[i-3] ^ W[i-8] ^ W[i-14] ^ W[i-16];
171
172 /* extra rotation fix */
173 W[i] = R32(W[i], 1);
174 }
175 A = sha_info->digest[0];
176 B = sha_info->digest[1];
177 C = sha_info->digest[2];
178 D = sha_info->digest[3];
179 E = sha_info->digest[4];
180 WP = W;
181 #ifdef UNRAVEL
182 FA(1); FB(1); FC(1); FD(1); FE(1); FT(1); FA(1); FB(1); FC(1); FD(1);
183 FE(1); FT(1); FA(1); FB(1); FC(1); FD(1); FE(1); FT(1); FA(1); FB(1);
184 FC(2); FD(2); FE(2); FT(2); FA(2); FB(2); FC(2); FD(2); FE(2); FT(2);
185 FA(2); FB(2); FC(2); FD(2); FE(2); FT(2); FA(2); FB(2); FC(2); FD(2);
186 FE(3); FT(3); FA(3); FB(3); FC(3); FD(3); FE(3); FT(3); FA(3); FB(3);
187 FC(3); FD(3); FE(3); FT(3); FA(3); FB(3); FC(3); FD(3); FE(3); FT(3);
188 FA(4); FB(4); FC(4); FD(4); FE(4); FT(4); FA(4); FB(4); FC(4); FD(4);
189 FE(4); FT(4); FA(4); FB(4); FC(4); FD(4); FE(4); FT(4); FA(4); FB(4);
190 sha_info->digest[0] += E;
191 sha_info->digest[1] += T;
192 sha_info->digest[2] += A;
193 sha_info->digest[3] += B;
194 sha_info->digest[4] += C;
195 #else /* !UNRAVEL */
196 #ifdef UNROLL_LOOPS
197 FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1);
198 FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1);
199 FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2);
200 FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2);
201 FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3);
202 FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3);
203 FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4);
204 FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4);
205 #else /* !UNROLL_LOOPS */
206 for (i = 0; i < 20; ++i) { FG(1); }
207 for (i = 20; i < 40; ++i) { FG(2); }
208 for (i = 40; i < 60; ++i) { FG(3); }
209 for (i = 60; i < 80; ++i) { FG(4); }
210 #endif /* !UNROLL_LOOPS */
211 sha_info->digest[0] += A;
212 sha_info->digest[1] += B;
213 sha_info->digest[2] += C;
214 sha_info->digest[3] += D;
215 sha_info->digest[4] += E;
216 #endif /* !UNRAVEL */
217 }
218
219 /* initialize the SHA digest */
220
221 static void
222 sha_init(SHAobject *sha_info)
223 {
224 TestEndianness(sha_info->Endianness)
225
226 sha_info->digest[0] = 0x67452301L;
227 sha_info->digest[1] = 0xefcdab89L;
228 sha_info->digest[2] = 0x98badcfeL;
229 sha_info->digest[3] = 0x10325476L;
230 sha_info->digest[4] = 0xc3d2e1f0L;
231 sha_info->count_lo = 0L;
232 sha_info->count_hi = 0L;
233 sha_info->local = 0;
234 }
235
236 /* update the SHA digest */
237
238 static void
239 sha_update(SHAobject *sha_info, SHA_BYTE *buffer, unsigned int count)
240 {
241 unsigned int i;
242 SHA_INT32 clo;
243
244 clo = sha_info->count_lo + ((SHA_INT32) count << 3);
245 if (clo < sha_info->count_lo) {
246 ++sha_info->count_hi;
247 }
248 sha_info->count_lo = clo;
249 sha_info->count_hi += (SHA_INT32) count >> 29;
250 if (sha_info->local) {
251 i = SHA_BLOCKSIZE - sha_info->local;
252 if (i > count) {
253 i = count;
254 }
255 memcpy(((SHA_BYTE *) sha_info->data) + sha_info->local, buffer, i);
256 count -= i;
257 buffer += i;
258 sha_info->local += i;
259 if (sha_info->local == SHA_BLOCKSIZE) {
260 sha_transform(sha_info);
261 }
262 else {
263 return;
264 }
265 }
266 while (count >= SHA_BLOCKSIZE) {
267 memcpy(sha_info->data, buffer, SHA_BLOCKSIZE);
268 buffer += SHA_BLOCKSIZE;
269 count -= SHA_BLOCKSIZE;
270 sha_transform(sha_info);
271 }
272 memcpy(sha_info->data, buffer, count);
273 sha_info->local = count;
274 }
275
276 /* finish computing the SHA digest */
277
278 static void
279 sha_final(unsigned char digest[20], SHAobject *sha_info)
280 {
281 int count;
282 SHA_INT32 lo_bit_count, hi_bit_count;
283
284 lo_bit_count = sha_info->count_lo;
285 hi_bit_count = sha_info->count_hi;
286 count = (int) ((lo_bit_count >> 3) & 0x3f);
287 ((SHA_BYTE *) sha_info->data)[count++] = 0x80;
288 if (count > SHA_BLOCKSIZE - 8) {
289 memset(((SHA_BYTE *) sha_info->data) + count, 0,
290 SHA_BLOCKSIZE - count);
291 sha_transform(sha_info);
292 memset((SHA_BYTE *) sha_info->data, 0, SHA_BLOCKSIZE - 8);
293 }
294 else {
295 memset(((SHA_BYTE *) sha_info->data) + count, 0,
296 SHA_BLOCKSIZE - 8 - count);
297 }
298
299 /* GJS: note that we add the hi/lo in big-endian. sha_transform will
300 swap these values into host-order. */
301 sha_info->data[56] = (hi_bit_count >> 24) & 0xff;
302 sha_info->data[57] = (hi_bit_count >> 16) & 0xff;
303 sha_info->data[58] = (hi_bit_count >> 8) & 0xff;
304 sha_info->data[59] = (hi_bit_count >> 0) & 0xff;
305 sha_info->data[60] = (lo_bit_count >> 24) & 0xff;
306 sha_info->data[61] = (lo_bit_count >> 16) & 0xff;
307 sha_info->data[62] = (lo_bit_count >> 8) & 0xff;
308 sha_info->data[63] = (lo_bit_count >> 0) & 0xff;
309 sha_transform(sha_info);
310 digest[ 0] = (unsigned char) ((sha_info->digest[0] >> 24) & 0xff);
311 digest[ 1] = (unsigned char) ((sha_info->digest[0] >> 16) & 0xff);
312 digest[ 2] = (unsigned char) ((sha_info->digest[0] >> 8) & 0xff);
313 digest[ 3] = (unsigned char) ((sha_info->digest[0] ) & 0xff);
314 digest[ 4] = (unsigned char) ((sha_info->digest[1] >> 24) & 0xff);
315 digest[ 5] = (unsigned char) ((sha_info->digest[1] >> 16) & 0xff);
316 digest[ 6] = (unsigned char) ((sha_info->digest[1] >> 8) & 0xff);
317 digest[ 7] = (unsigned char) ((sha_info->digest[1] ) & 0xff);
318 digest[ 8] = (unsigned char) ((sha_info->digest[2] >> 24) & 0xff);
319 digest[ 9] = (unsigned char) ((sha_info->digest[2] >> 16) & 0xff);
320 digest[10] = (unsigned char) ((sha_info->digest[2] >> 8) & 0xff);
321 digest[11] = (unsigned char) ((sha_info->digest[2] ) & 0xff);
322 digest[12] = (unsigned char) ((sha_info->digest[3] >> 24) & 0xff);
323 digest[13] = (unsigned char) ((sha_info->digest[3] >> 16) & 0xff);
324 digest[14] = (unsigned char) ((sha_info->digest[3] >> 8) & 0xff);
325 digest[15] = (unsigned char) ((sha_info->digest[3] ) & 0xff);
326 digest[16] = (unsigned char) ((sha_info->digest[4] >> 24) & 0xff);
327 digest[17] = (unsigned char) ((sha_info->digest[4] >> 16) & 0xff);
328 digest[18] = (unsigned char) ((sha_info->digest[4] >> 8) & 0xff);
329 digest[19] = (unsigned char) ((sha_info->digest[4] ) & 0xff);
330 }
331
332 /*
333 * End of copied SHA code.
334 *
335 * ------------------------------------------------------------------------
336 */
337
338 static PyTypeObject SHAtype;
339
340
341 static SHAobject *
342 newSHAobject(void)
343 {
344 return (SHAobject *)PyObject_New(SHAobject, &SHAtype);
345 }
346
347 /* Internal methods for a hashing object */
348
349 static void
350 SHA_dealloc(PyObject *ptr)
351 {
352 PyObject_Del(ptr);
353 }
354
355
356 /* External methods for a hashing object */
357
358 PyDoc_STRVAR(SHA_copy__doc__, "Return a copy of the hashing object.");
359
360 static PyObject *
361 SHA_copy(SHAobject *self, PyObject *unused)
362 {
363 SHAobject *newobj;
364
365 if ( (newobj = newSHAobject())==NULL)
366 return NULL;
367
368 SHAcopy(self, newobj);
369 return (PyObject *)newobj;
370 }
371
372 PyDoc_STRVAR(SHA_digest__doc__,
373 "Return the digest value as a string of binary data.");
374
375 static PyObject *
376 SHA_digest(SHAobject *self, PyObject *unused)
377 {
378 unsigned char digest[SHA_DIGESTSIZE];
379 SHAobject temp;
380
381 SHAcopy(self, &temp);
382 sha_final(digest, &temp);
383 return PyString_FromStringAndSize((const char *)digest, sizeof(digest));
384 }
385
386 PyDoc_STRVAR(SHA_hexdigest__doc__,
387 "Return the digest value as a string of hexadecimal digits.");
388
389 static PyObject *
390 SHA_hexdigest(SHAobject *self, PyObject *unused)
391 {
392 unsigned char digest[SHA_DIGESTSIZE];
393 SHAobject temp;
394 PyObject *retval;
395 char *hex_digest;
396 int i, j;
397
398 /* Get the raw (binary) digest value */
399 SHAcopy(self, &temp);
400 sha_final(digest, &temp);
401
402 /* Create a new string */
403 retval = PyString_FromStringAndSize(NULL, sizeof(digest) * 2);
404 if (!retval)
405 return NULL;
406 hex_digest = PyString_AsString(retval);
407 if (!hex_digest) {
408 Py_DECREF(retval);
409 return NULL;
410 }
411
412 /* Make hex version of the digest */
413 for(i=j=0; i<sizeof(digest); i++) {
414 char c;
415 c = (digest[i] >> 4) & 0xf;
416 c = (c>9) ? c+'a'-10 : c + '0';
417 hex_digest[j++] = c;
418 c = (digest[i] & 0xf);
419 c = (c>9) ? c+'a'-10 : c + '0';
420 hex_digest[j++] = c;
421 }
422 return retval;
423 }
424
425 PyDoc_STRVAR(SHA_update__doc__,
426 "Update this hashing object's state with the provided string.");
427
428 static PyObject *
429 SHA_update(SHAobject *self, PyObject *args)
430 {
431 Py_buffer view;
432 Py_ssize_t n;
433 unsigned char *buf;
434
435 if (!PyArg_ParseTuple(args, "s*:update", &view))
436 return NULL;
437
438 n = view.len;
439 buf = (unsigned char *) view.buf;
440 while (n > 0) {
441 Py_ssize_t nbytes;
442 if (n > INT_MAX)
443 nbytes = INT_MAX;
444 else
445 nbytes = n;
446 sha_update(self, buf,
447 Py_SAFE_DOWNCAST(nbytes, Py_ssize_t, unsigned int));
448 buf += nbytes;
449 n -= nbytes;
450 }
451
452 PyBuffer_Release(&view);
453 Py_RETURN_NONE;
454 }
455
456 static PyMethodDef SHA_methods[] = {
457 {"copy", (PyCFunction)SHA_copy, METH_NOARGS, SHA_copy__doc__},
458 {"digest", (PyCFunction)SHA_digest, METH_NOARGS, SHA_digest__doc__},
459 {"hexdigest", (PyCFunction)SHA_hexdigest, METH_NOARGS, SHA_hexdigest__doc__},
460 {"update", (PyCFunction)SHA_update, METH_VARARGS, SHA_update__doc__},
461 {NULL, NULL} /* sentinel */
462 };
463
464 static PyObject *
465 SHA_get_block_size(PyObject *self, void *closure)
466 {
467 return PyInt_FromLong(SHA_BLOCKSIZE);
468 }
469
470 static PyObject *
471 SHA_get_digest_size(PyObject *self, void *closure)
472 {
473 return PyInt_FromLong(SHA_DIGESTSIZE);
474 }
475
476 static PyObject *
477 SHA_get_name(PyObject *self, void *closure)
478 {
479 return PyString_FromStringAndSize("SHA1", 4);
480 }
481
482 static PyGetSetDef SHA_getseters[] = {
483 {"digest_size",
484 (getter)SHA_get_digest_size, NULL,
485 NULL,
486 NULL},
487 {"block_size",
488 (getter)SHA_get_block_size, NULL,
489 NULL,
490 NULL},
491 {"name",
492 (getter)SHA_get_name, NULL,
493 NULL,
494 NULL},
495 /* the old md5 and sha modules support 'digest_size' as in PEP 247.
496 * the old sha module also supported 'digestsize'. ugh. */
497 {"digestsize",
498 (getter)SHA_get_digest_size, NULL,
499 NULL,
500 NULL},
501 {NULL} /* Sentinel */
502 };
503
504 static PyTypeObject SHAtype = {
505 PyVarObject_HEAD_INIT(NULL, 0)
506 "_sha.sha", /*tp_name*/
507 sizeof(SHAobject), /*tp_size*/
508 0, /*tp_itemsize*/
509 /* methods */
510 SHA_dealloc, /*tp_dealloc*/
511 0, /*tp_print*/
512 0, /*tp_getattr*/
513 0, /*tp_setattr*/
514 0, /*tp_compare*/
515 0, /*tp_repr*/
516 0, /*tp_as_number*/
517 0, /*tp_as_sequence*/
518 0, /*tp_as_mapping*/
519 0, /*tp_hash*/
520 0, /*tp_call*/
521 0, /*tp_str*/
522 0, /*tp_getattro*/
523 0, /*tp_setattro*/
524 0, /*tp_as_buffer*/
525 Py_TPFLAGS_DEFAULT, /*tp_flags*/
526 0, /*tp_doc*/
527 0, /*tp_traverse*/
528 0, /*tp_clear*/
529 0, /*tp_richcompare*/
530 0, /*tp_weaklistoffset*/
531 0, /*tp_iter*/
532 0, /*tp_iternext*/
533 SHA_methods, /* tp_methods */
534 0, /* tp_members */
535 SHA_getseters, /* tp_getset */
536 };
537
538
539 /* The single module-level function: new() */
540
541 PyDoc_STRVAR(SHA_new__doc__,
542 "Return a new SHA hashing object. An optional string argument\n\
543 may be provided; if present, this string will be automatically\n\
544 hashed.");
545
546 static PyObject *
547 SHA_new(PyObject *self, PyObject *args, PyObject *kwdict)
548 {
549 static char *kwlist[] = {"string", NULL};
550 SHAobject *new;
551 Py_buffer view = { 0 };
552 Py_ssize_t n;
553 unsigned char *buf;
554
555 if (!PyArg_ParseTupleAndKeywords(args, kwdict, "|s*:new", kwlist,
556 &view)) {
557 return NULL;
558 }
559
560 if ((new = newSHAobject()) == NULL) {
561 PyBuffer_Release(&view);
562 return NULL;
563 }
564
565 sha_init(new);
566
567 if (PyErr_Occurred()) {
568 Py_DECREF(new);
569 PyBuffer_Release(&view);
570 return NULL;
571 }
572
573 n = view.len;
574 buf = (unsigned char *) view.buf;
575 while (n > 0) {
576 Py_ssize_t nbytes;
577 if (n > INT_MAX)
578 nbytes = INT_MAX;
579 else
580 nbytes = n;
581 sha_update(new, buf,
582 Py_SAFE_DOWNCAST(nbytes, Py_ssize_t, unsigned int));
583 buf += nbytes;
584 n -= nbytes;
585 }
586
587 PyBuffer_Release(&view);
588
589 return (PyObject *)new;
590 }
591
592
593 /* List of functions exported by this module */
594
595 static struct PyMethodDef SHA_functions[] = {
596 {"new", (PyCFunction)SHA_new, METH_VARARGS|METH_KEYWORDS, SHA_new__doc__},
597 {NULL, NULL} /* Sentinel */
598 };
599
600
601 /* Initialize this module. */
602
603 #define insint(n,v) { PyModule_AddIntConstant(m,n,v); }
604
605 PyMODINIT_FUNC
606 init_sha(void)
607 {
608 PyObject *m;
609
610 Py_TYPE(&SHAtype) = &PyType_Type;
611 if (PyType_Ready(&SHAtype) < 0)
612 return;
613 m = Py_InitModule("_sha", SHA_functions);
614 if (m == NULL)
615 return;
616
617 /* Add some symbolic constants to the module */
618 insint("blocksize", 1); /* For future use, in case some hash
619 functions require an integral number of
620 blocks */
621 insint("digestsize", 20);
622 insint("digest_size", 20);
623 }