* grub-core/fs/udf.c: Add support for UUID
[grub.git] / grub-core / fs / udf.c
1 /* udf.c - Universal Disk Format filesystem.  */
2 /*
3  *  GRUB  --  GRand Unified Bootloader
4  *  Copyright (C) 2008,2009  Free Software Foundation, Inc.
5  *
6  *  GRUB is free software: you can redistribute it and/or modify
7  *  it under the terms of the GNU General Public License as published by
8  *  the Free Software Foundation, either version 3 of the License, or
9  *  (at your option) any later version.
10  *
11  *  GRUB is distributed in the hope that it will be useful,
12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  *  GNU General Public License for more details.
15  *
16  *  You should have received a copy of the GNU General Public License
17  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
18  */
19
20 #include <grub/err.h>
21 #include <grub/file.h>
22 #include <grub/mm.h>
23 #include <grub/misc.h>
24 #include <grub/disk.h>
25 #include <grub/dl.h>
26 #include <grub/types.h>
27 #include <grub/fshelp.h>
28 #include <grub/charset.h>
29 #include <grub/datetime.h>
30 #include <grub/udf.h>
31
32 GRUB_MOD_LICENSE ("GPLv3+");
33
34 #define GRUB_UDF_MAX_PDS                2
35 #define GRUB_UDF_MAX_PMS                6
36
37 #define U16                             grub_le_to_cpu16
38 #define U32                             grub_le_to_cpu32
39 #define U64                             grub_le_to_cpu64
40
41 #define GRUB_UDF_TAG_IDENT_PVD          0x0001
42 #define GRUB_UDF_TAG_IDENT_AVDP         0x0002
43 #define GRUB_UDF_TAG_IDENT_VDP          0x0003
44 #define GRUB_UDF_TAG_IDENT_IUVD         0x0004
45 #define GRUB_UDF_TAG_IDENT_PD           0x0005
46 #define GRUB_UDF_TAG_IDENT_LVD          0x0006
47 #define GRUB_UDF_TAG_IDENT_USD          0x0007
48 #define GRUB_UDF_TAG_IDENT_TD           0x0008
49 #define GRUB_UDF_TAG_IDENT_LVID         0x0009
50
51 #define GRUB_UDF_TAG_IDENT_FSD          0x0100
52 #define GRUB_UDF_TAG_IDENT_FID          0x0101
53 #define GRUB_UDF_TAG_IDENT_AED          0x0102
54 #define GRUB_UDF_TAG_IDENT_IE           0x0103
55 #define GRUB_UDF_TAG_IDENT_TE           0x0104
56 #define GRUB_UDF_TAG_IDENT_FE           0x0105
57 #define GRUB_UDF_TAG_IDENT_EAHD         0x0106
58 #define GRUB_UDF_TAG_IDENT_USE          0x0107
59 #define GRUB_UDF_TAG_IDENT_SBD          0x0108
60 #define GRUB_UDF_TAG_IDENT_PIE          0x0109
61 #define GRUB_UDF_TAG_IDENT_EFE          0x010A
62
63 #define GRUB_UDF_ICBTAG_TYPE_UNDEF      0x00
64 #define GRUB_UDF_ICBTAG_TYPE_USE        0x01
65 #define GRUB_UDF_ICBTAG_TYPE_PIE        0x02
66 #define GRUB_UDF_ICBTAG_TYPE_IE         0x03
67 #define GRUB_UDF_ICBTAG_TYPE_DIRECTORY  0x04
68 #define GRUB_UDF_ICBTAG_TYPE_REGULAR    0x05
69 #define GRUB_UDF_ICBTAG_TYPE_BLOCK      0x06
70 #define GRUB_UDF_ICBTAG_TYPE_CHAR       0x07
71 #define GRUB_UDF_ICBTAG_TYPE_EA         0x08
72 #define GRUB_UDF_ICBTAG_TYPE_FIFO       0x09
73 #define GRUB_UDF_ICBTAG_TYPE_SOCKET     0x0A
74 #define GRUB_UDF_ICBTAG_TYPE_TE         0x0B
75 #define GRUB_UDF_ICBTAG_TYPE_SYMLINK    0x0C
76 #define GRUB_UDF_ICBTAG_TYPE_STREAMDIR  0x0D
77
78 #define GRUB_UDF_ICBTAG_FLAG_AD_MASK    0x0007
79 #define GRUB_UDF_ICBTAG_FLAG_AD_SHORT   0x0000
80 #define GRUB_UDF_ICBTAG_FLAG_AD_LONG    0x0001
81 #define GRUB_UDF_ICBTAG_FLAG_AD_EXT     0x0002
82 #define GRUB_UDF_ICBTAG_FLAG_AD_IN_ICB  0x0003
83
84 #define GRUB_UDF_EXT_NORMAL             0x00000000
85 #define GRUB_UDF_EXT_NREC_ALLOC         0x40000000
86 #define GRUB_UDF_EXT_NREC_NALLOC        0x80000000
87 #define GRUB_UDF_EXT_MASK               0xC0000000
88
89 #define GRUB_UDF_FID_CHAR_HIDDEN        0x01
90 #define GRUB_UDF_FID_CHAR_DIRECTORY     0x02
91 #define GRUB_UDF_FID_CHAR_DELETED       0x04
92 #define GRUB_UDF_FID_CHAR_PARENT        0x08
93 #define GRUB_UDF_FID_CHAR_METADATA      0x10
94
95 #define GRUB_UDF_STD_IDENT_BEA01        "BEA01"
96 #define GRUB_UDF_STD_IDENT_BOOT2        "BOOT2"
97 #define GRUB_UDF_STD_IDENT_CD001        "CD001"
98 #define GRUB_UDF_STD_IDENT_CDW02        "CDW02"
99 #define GRUB_UDF_STD_IDENT_NSR02        "NSR02"
100 #define GRUB_UDF_STD_IDENT_NSR03        "NSR03"
101 #define GRUB_UDF_STD_IDENT_TEA01        "TEA01"
102
103 #define GRUB_UDF_CHARSPEC_TYPE_CS0      0x00
104 #define GRUB_UDF_CHARSPEC_TYPE_CS1      0x01
105 #define GRUB_UDF_CHARSPEC_TYPE_CS2      0x02
106 #define GRUB_UDF_CHARSPEC_TYPE_CS3      0x03
107 #define GRUB_UDF_CHARSPEC_TYPE_CS4      0x04
108 #define GRUB_UDF_CHARSPEC_TYPE_CS5      0x05
109 #define GRUB_UDF_CHARSPEC_TYPE_CS6      0x06
110 #define GRUB_UDF_CHARSPEC_TYPE_CS7      0x07
111 #define GRUB_UDF_CHARSPEC_TYPE_CS8      0x08
112
113 #define GRUB_UDF_PARTMAP_TYPE_1         1
114 #define GRUB_UDF_PARTMAP_TYPE_2         2
115
116 struct grub_udf_lb_addr
117 {
118   grub_uint32_t block_num;
119   grub_uint16_t part_ref;
120 } GRUB_PACKED;
121
122 struct grub_udf_short_ad
123 {
124   grub_uint32_t length;
125   grub_uint32_t position;
126 } GRUB_PACKED;
127
128 struct grub_udf_long_ad
129 {
130   grub_uint32_t length;
131   struct grub_udf_lb_addr block;
132   grub_uint8_t imp_use[6];
133 } GRUB_PACKED;
134
135 struct grub_udf_extent_ad
136 {
137   grub_uint32_t length;
138   grub_uint32_t start;
139 } GRUB_PACKED;
140
141 struct grub_udf_charspec
142 {
143   grub_uint8_t charset_type;
144   grub_uint8_t charset_info[63];
145 } GRUB_PACKED;
146
147 struct grub_udf_timestamp
148 {
149   grub_uint16_t type_and_timezone;
150   grub_uint16_t year;
151   grub_uint8_t month;
152   grub_uint8_t day;
153   grub_uint8_t hour;
154   grub_uint8_t minute;
155   grub_uint8_t second;
156   grub_uint8_t centi_seconds;
157   grub_uint8_t hundreds_of_micro_seconds;
158   grub_uint8_t micro_seconds;
159 } GRUB_PACKED;
160
161 struct grub_udf_regid
162 {
163   grub_uint8_t flags;
164   grub_uint8_t ident[23];
165   grub_uint8_t ident_suffix[8];
166 } GRUB_PACKED;
167
168 struct grub_udf_tag
169 {
170   grub_uint16_t tag_ident;
171   grub_uint16_t desc_version;
172   grub_uint8_t tag_checksum;
173   grub_uint8_t reserved;
174   grub_uint16_t tag_serial_number;
175   grub_uint16_t desc_crc;
176   grub_uint16_t desc_crc_length;
177   grub_uint32_t tag_location;
178 } GRUB_PACKED;
179
180 struct grub_udf_fileset
181 {
182   struct grub_udf_tag tag;
183   struct grub_udf_timestamp datetime;
184   grub_uint16_t interchange_level;
185   grub_uint16_t max_interchange_level;
186   grub_uint32_t charset_list;
187   grub_uint32_t max_charset_list;
188   grub_uint32_t fileset_num;
189   grub_uint32_t fileset_desc_num;
190   struct grub_udf_charspec vol_charset;
191   grub_uint8_t vol_ident[128];
192   struct grub_udf_charspec fileset_charset;
193   grub_uint8_t fileset_ident[32];
194   grub_uint8_t copyright_file_ident[32];
195   grub_uint8_t abstract_file_ident[32];
196   struct grub_udf_long_ad root_icb;
197   struct grub_udf_regid domain_ident;
198   struct grub_udf_long_ad next_ext;
199   struct grub_udf_long_ad streamdir_icb;
200 } GRUB_PACKED;
201
202 struct grub_udf_icbtag
203 {
204   grub_uint32_t prior_recorded_num_direct_entries;
205   grub_uint16_t strategy_type;
206   grub_uint16_t strategy_parameter;
207   grub_uint16_t num_entries;
208   grub_uint8_t reserved;
209   grub_uint8_t file_type;
210   struct grub_udf_lb_addr parent_idb;
211   grub_uint16_t flags;
212 } GRUB_PACKED;
213
214 struct grub_udf_file_ident
215 {
216   struct grub_udf_tag tag;
217   grub_uint16_t version_num;
218   grub_uint8_t characteristics;
219 #define MAX_FILE_IDENT_LENGTH 256
220   grub_uint8_t file_ident_length;
221   struct grub_udf_long_ad icb;
222   grub_uint16_t imp_use_length;
223 } GRUB_PACKED;
224
225 struct grub_udf_file_entry
226 {
227   struct grub_udf_tag tag;
228   struct grub_udf_icbtag icbtag;
229   grub_uint32_t uid;
230   grub_uint32_t gid;
231   grub_uint32_t permissions;
232   grub_uint16_t link_count;
233   grub_uint8_t record_format;
234   grub_uint8_t record_display_attr;
235   grub_uint32_t record_length;
236   grub_uint64_t file_size;
237   grub_uint64_t blocks_recorded;
238   struct grub_udf_timestamp access_time;
239   struct grub_udf_timestamp modification_time;
240   struct grub_udf_timestamp attr_time;
241   grub_uint32_t checkpoint;
242   struct grub_udf_long_ad extended_attr_idb;
243   struct grub_udf_regid imp_ident;
244   grub_uint64_t unique_id;
245   grub_uint32_t ext_attr_length;
246   grub_uint32_t alloc_descs_length;
247   grub_uint8_t ext_attr[0];
248 } GRUB_PACKED;
249
250 struct grub_udf_extended_file_entry
251 {
252   struct grub_udf_tag tag;
253   struct grub_udf_icbtag icbtag;
254   grub_uint32_t uid;
255   grub_uint32_t gid;
256   grub_uint32_t permissions;
257   grub_uint16_t link_count;
258   grub_uint8_t record_format;
259   grub_uint8_t record_display_attr;
260   grub_uint32_t record_length;
261   grub_uint64_t file_size;
262   grub_uint64_t object_size;
263   grub_uint64_t blocks_recorded;
264   struct grub_udf_timestamp access_time;
265   struct grub_udf_timestamp modification_time;
266   struct grub_udf_timestamp create_time;
267   struct grub_udf_timestamp attr_time;
268   grub_uint32_t checkpoint;
269   grub_uint32_t reserved;
270   struct grub_udf_long_ad extended_attr_icb;
271   struct grub_udf_long_ad streamdir_icb;
272   struct grub_udf_regid imp_ident;
273   grub_uint64_t unique_id;
274   grub_uint32_t ext_attr_length;
275   grub_uint32_t alloc_descs_length;
276   grub_uint8_t ext_attr[0];
277 } GRUB_PACKED;
278
279 struct grub_udf_vrs
280 {
281   grub_uint8_t type;
282   grub_uint8_t magic[5];
283   grub_uint8_t version;
284 } GRUB_PACKED;
285
286 struct grub_udf_avdp
287 {
288   struct grub_udf_tag tag;
289   struct grub_udf_extent_ad vds;
290 } GRUB_PACKED;
291
292 struct grub_udf_pd
293 {
294   struct grub_udf_tag tag;
295   grub_uint32_t seq_num;
296   grub_uint16_t flags;
297   grub_uint16_t part_num;
298   struct grub_udf_regid contents;
299   grub_uint8_t contents_use[128];
300   grub_uint32_t access_type;
301   grub_uint32_t start;
302   grub_uint32_t length;
303 } GRUB_PACKED;
304
305 struct grub_udf_partmap
306 {
307   grub_uint8_t type;
308   grub_uint8_t length;
309   union
310   {
311     struct
312     {
313       grub_uint16_t seq_num;
314       grub_uint16_t part_num;
315     } type1;
316
317     struct
318     {
319       grub_uint8_t ident[62];
320     } type2;
321   };
322 } GRUB_PACKED;
323
324 struct grub_udf_pvd
325 {
326   struct grub_udf_tag tag;
327   grub_uint32_t seq_num;
328   grub_uint32_t pvd_num;
329   grub_uint8_t ident[32];
330   grub_uint16_t vol_seq_num;
331   grub_uint16_t max_vol_seq_num;
332   grub_uint16_t interchange_level;
333   grub_uint16_t max_interchange_level;
334   grub_uint32_t charset_list;
335   grub_uint32_t max_charset_list;
336   grub_uint8_t volset_ident[128];
337   struct grub_udf_charspec desc_charset;
338   struct grub_udf_charspec expl_charset;
339   struct grub_udf_extent_ad vol_abstract;
340   struct grub_udf_extent_ad vol_copyright;
341   struct grub_udf_regid app_ident;
342   struct grub_udf_timestamp recording_time;
343   struct grub_udf_regid imp_ident;
344   grub_uint8_t imp_use[64];
345   grub_uint32_t pred_vds_loc;
346   grub_uint16_t flags;
347   grub_uint8_t reserved[22];
348 } GRUB_PACKED;
349
350 struct grub_udf_lvd
351 {
352   struct grub_udf_tag tag;
353   grub_uint32_t seq_num;
354   struct grub_udf_charspec charset;
355   grub_uint8_t ident[128];
356   grub_uint32_t bsize;
357   struct grub_udf_regid domain_ident;
358   struct grub_udf_long_ad root_fileset;
359   grub_uint32_t map_table_length;
360   grub_uint32_t num_part_maps;
361   struct grub_udf_regid imp_ident;
362   grub_uint8_t imp_use[128];
363   struct grub_udf_extent_ad integrity_seq_ext;
364   grub_uint8_t part_maps[1608];
365 } GRUB_PACKED;
366
367 struct grub_udf_aed
368 {
369   struct grub_udf_tag tag;
370   grub_uint32_t prev_ae;
371   grub_uint32_t ae_len;
372 } GRUB_PACKED;
373
374 struct grub_udf_data
375 {
376   grub_disk_t disk;
377   struct grub_udf_pvd pvd;
378   struct grub_udf_lvd lvd;
379   struct grub_udf_pd pds[GRUB_UDF_MAX_PDS];
380   struct grub_udf_partmap *pms[GRUB_UDF_MAX_PMS];
381   struct grub_udf_long_ad root_icb;
382   int npd, npm, lbshift;
383 };
384
385 struct grub_fshelp_node
386 {
387   struct grub_udf_data *data;
388   int part_ref;
389   union
390   {
391     struct grub_udf_file_entry fe;
392     struct grub_udf_extended_file_entry efe;
393     char raw[0];
394   } block;
395 };
396
397 static inline grub_size_t
398 get_fshelp_size (struct grub_udf_data *data)
399 {
400   struct grub_fshelp_node *x = NULL;
401   return sizeof (*x)
402     + (1 << (GRUB_DISK_SECTOR_BITS
403              + data->lbshift)) - sizeof (x->block);
404 }
405
406 static grub_dl_t my_mod;
407
408 static grub_uint32_t
409 grub_udf_get_block (struct grub_udf_data *data,
410                     grub_uint16_t part_ref, grub_uint32_t block)
411 {
412   part_ref = U16 (part_ref);
413
414   if (part_ref >= data->npm)
415     {
416       grub_error (GRUB_ERR_BAD_FS, "invalid part ref");
417       return 0;
418     }
419
420   return (U32 (data->pds[data->pms[part_ref]->type1.part_num].start)
421           + U32 (block));
422 }
423
424 static grub_err_t
425 grub_udf_read_icb (struct grub_udf_data *data,
426                    struct grub_udf_long_ad *icb,
427                    struct grub_fshelp_node *node)
428 {
429   grub_uint32_t block;
430
431   block = grub_udf_get_block (data,
432                               icb->block.part_ref,
433                               icb->block.block_num);
434
435   if (grub_errno)
436     return grub_errno;
437
438   if (grub_disk_read (data->disk, block << data->lbshift, 0,
439                       1 << (GRUB_DISK_SECTOR_BITS
440                             + data->lbshift),
441                       &node->block))
442     return grub_errno;
443
444   if ((U16 (node->block.fe.tag.tag_ident) != GRUB_UDF_TAG_IDENT_FE) &&
445       (U16 (node->block.fe.tag.tag_ident) != GRUB_UDF_TAG_IDENT_EFE))
446     return grub_error (GRUB_ERR_BAD_FS, "invalid fe/efe descriptor");
447
448   node->part_ref = icb->block.part_ref;
449   node->data = data;
450   return 0;
451 }
452
453 static grub_disk_addr_t
454 grub_udf_read_block (grub_fshelp_node_t node, grub_disk_addr_t fileblock)
455 {
456   char *buf = NULL;
457   char *ptr;
458   grub_ssize_t len;
459   grub_disk_addr_t filebytes;
460
461   switch (U16 (node->block.fe.tag.tag_ident))
462     {
463     case GRUB_UDF_TAG_IDENT_FE:
464       ptr = (char *) &node->block.fe.ext_attr[0] + U32 (node->block.fe.ext_attr_length);
465       len = U32 (node->block.fe.alloc_descs_length);
466       break;
467
468     case GRUB_UDF_TAG_IDENT_EFE:
469       ptr = (char *) &node->block.efe.ext_attr[0] + U32 (node->block.efe.ext_attr_length);
470       len = U32 (node->block.efe.alloc_descs_length);
471       break;
472
473     default:
474       grub_error (GRUB_ERR_BAD_FS, "invalid file entry");
475       return 0;
476     }
477
478   if ((U16 (node->block.fe.icbtag.flags) & GRUB_UDF_ICBTAG_FLAG_AD_MASK)
479       == GRUB_UDF_ICBTAG_FLAG_AD_SHORT)
480     {
481       struct grub_udf_short_ad *ad = (struct grub_udf_short_ad *) ptr;
482
483       filebytes = fileblock * U32 (node->data->lvd.bsize);
484       while (len >= (grub_ssize_t) sizeof (struct grub_udf_short_ad))
485         {
486           grub_uint32_t adlen = U32 (ad->length) & 0x3fffffff;
487           grub_uint32_t adtype = U32 (ad->length) >> 30;
488           if (adtype == 3)
489             {
490               struct grub_udf_aed *extension;
491               grub_disk_addr_t sec = grub_udf_get_block(node->data,
492                                                         node->part_ref,
493                                                         ad->position);
494               if (!buf)
495                 {
496                   buf = grub_malloc (U32 (node->data->lvd.bsize));
497                   if (!buf)
498                     return 0;
499                 }
500               if (grub_disk_read (node->data->disk, sec << node->data->lbshift,
501                                   0, adlen, buf))
502                 goto fail;
503
504               extension = (struct grub_udf_aed *) buf;
505               if (U16 (extension->tag.tag_ident) != GRUB_UDF_TAG_IDENT_AED)
506                 {
507                   grub_error (GRUB_ERR_BAD_FS, "invalid aed tag");
508                   goto fail;
509                 }
510
511               len = U32 (extension->ae_len);
512               ad = (struct grub_udf_short_ad *)
513                     (buf + sizeof (struct grub_udf_aed));
514               continue;
515             }
516
517           if (filebytes < adlen)
518             {
519               grub_uint32_t ad_pos = ad->position;
520               grub_free (buf);
521               return ((U32 (ad_pos) & GRUB_UDF_EXT_MASK) ? 0 :
522                       (grub_udf_get_block (node->data, node->part_ref, ad_pos)
523                        + (filebytes >> (GRUB_DISK_SECTOR_BITS
524                                         + node->data->lbshift))));
525             }
526
527           filebytes -= adlen;
528           ad++;
529           len -= sizeof (struct grub_udf_short_ad);
530         }
531     }
532   else
533     {
534       struct grub_udf_long_ad *ad = (struct grub_udf_long_ad *) ptr;
535
536       filebytes = fileblock * U32 (node->data->lvd.bsize);
537       while (len >= (grub_ssize_t) sizeof (struct grub_udf_long_ad))
538         {
539           grub_uint32_t adlen = U32 (ad->length) & 0x3fffffff;
540           grub_uint32_t adtype = U32 (ad->length) >> 30;
541           if (adtype == 3)
542             {
543               struct grub_udf_aed *extension;
544               grub_disk_addr_t sec = grub_udf_get_block(node->data,
545                                                         ad->block.part_ref,
546                                                         ad->block.block_num);
547               if (!buf)
548                 {
549                   buf = grub_malloc (U32 (node->data->lvd.bsize));
550                   if (!buf)
551                     return 0;
552                 }
553               if (grub_disk_read (node->data->disk, sec << node->data->lbshift,
554                                   0, adlen, buf))
555                 goto fail;
556
557               extension = (struct grub_udf_aed *) buf;
558               if (U16 (extension->tag.tag_ident) != GRUB_UDF_TAG_IDENT_AED)
559                 {
560                   grub_error (GRUB_ERR_BAD_FS, "invalid aed tag");
561                   goto fail;
562                 }
563
564               len = U32 (extension->ae_len);
565               ad = (struct grub_udf_long_ad *)
566                     (buf + sizeof (struct grub_udf_aed));
567               continue;
568             }
569               
570           if (filebytes < adlen)
571             {
572               grub_uint32_t ad_block_num = ad->block.block_num;
573               grub_uint32_t ad_part_ref = ad->block.part_ref;
574               grub_free (buf);
575               return ((U32 (ad_block_num) & GRUB_UDF_EXT_MASK) ?  0 :
576                       (grub_udf_get_block (node->data, ad_part_ref,
577                                            ad_block_num)
578                        + (filebytes >> (GRUB_DISK_SECTOR_BITS
579                                         + node->data->lbshift))));
580             }
581
582           filebytes -= adlen;
583           ad++;
584           len -= sizeof (struct grub_udf_long_ad);
585         }
586     }
587
588 fail:
589   grub_free (buf);
590
591   return 0;
592 }
593
594 static grub_ssize_t
595 grub_udf_read_file (grub_fshelp_node_t node,
596                     grub_disk_read_hook_t read_hook, void *read_hook_data,
597                     grub_off_t pos, grub_size_t len, char *buf)
598 {
599   switch (U16 (node->block.fe.icbtag.flags) & GRUB_UDF_ICBTAG_FLAG_AD_MASK)
600     {
601     case GRUB_UDF_ICBTAG_FLAG_AD_IN_ICB:
602       {
603         char *ptr;
604
605         ptr = ((U16 (node->block.fe.tag.tag_ident) == GRUB_UDF_TAG_IDENT_FE) ?
606                ((char *) &node->block.fe.ext_attr[0]
607                 + U32 (node->block.fe.ext_attr_length)) :
608                ((char *) &node->block.efe.ext_attr[0]
609                 + U32 (node->block.efe.ext_attr_length)));
610
611         grub_memcpy (buf, ptr + pos, len);
612
613         return len;
614       }
615
616     case GRUB_UDF_ICBTAG_FLAG_AD_EXT:
617       grub_error (GRUB_ERR_BAD_FS, "invalid extent type");
618       return 0;
619     }
620
621   return grub_fshelp_read_file (node->data->disk, node,
622                                 read_hook, read_hook_data,
623                                 pos, len, buf, grub_udf_read_block,
624                                 U64 (node->block.fe.file_size),
625                                 node->data->lbshift, 0);
626 }
627
628 static unsigned sblocklist[] = { 256, 512, 0 };
629
630 static struct grub_udf_data *
631 grub_udf_mount (grub_disk_t disk)
632 {
633   struct grub_udf_data *data = 0;
634   struct grub_udf_fileset root_fs;
635   unsigned *sblklist;
636   grub_uint32_t block, vblock;
637   int i, lbshift;
638
639   data = grub_malloc (sizeof (struct grub_udf_data));
640   if (!data)
641     return 0;
642
643   data->disk = disk;
644
645   /* Search for Anchor Volume Descriptor Pointer (AVDP)
646    * and determine logical block size.  */
647   block = 0;
648   for (lbshift = 0; lbshift < 4; lbshift++)
649     {
650       for (sblklist = sblocklist; *sblklist; sblklist++)
651         {
652           struct grub_udf_avdp avdp;
653
654           if (grub_disk_read (disk, *sblklist << lbshift, 0,
655                               sizeof (struct grub_udf_avdp), &avdp))
656             {
657               grub_error (GRUB_ERR_BAD_FS, "not an UDF filesystem");
658               goto fail;
659             }
660
661           if (U16 (avdp.tag.tag_ident) == GRUB_UDF_TAG_IDENT_AVDP &&
662               U32 (avdp.tag.tag_location) == *sblklist)
663             {
664               block = U32 (avdp.vds.start);
665               break;
666             }
667         }
668
669       if (block)
670         break;
671     }
672
673   if (!block)
674     {
675       grub_error (GRUB_ERR_BAD_FS, "not an UDF filesystem");
676       goto fail;
677     }
678   data->lbshift = lbshift;
679
680   /* Search for Volume Recognition Sequence (VRS).  */
681   for (vblock = (32767 >> (lbshift + GRUB_DISK_SECTOR_BITS)) + 1;;
682        vblock += (2047 >> (lbshift + GRUB_DISK_SECTOR_BITS)) + 1)
683     {
684       struct grub_udf_vrs vrs;
685
686       if (grub_disk_read (disk, vblock << lbshift, 0,
687                           sizeof (struct grub_udf_vrs), &vrs))
688         {
689           grub_error (GRUB_ERR_BAD_FS, "not an UDF filesystem");
690           goto fail;
691         }
692
693       if ((!grub_memcmp (vrs.magic, GRUB_UDF_STD_IDENT_NSR03, 5)) ||
694           (!grub_memcmp (vrs.magic, GRUB_UDF_STD_IDENT_NSR02, 5)))
695         break;
696
697       if ((grub_memcmp (vrs.magic, GRUB_UDF_STD_IDENT_BEA01, 5)) &&
698           (grub_memcmp (vrs.magic, GRUB_UDF_STD_IDENT_BOOT2, 5)) &&
699           (grub_memcmp (vrs.magic, GRUB_UDF_STD_IDENT_CD001, 5)) &&
700           (grub_memcmp (vrs.magic, GRUB_UDF_STD_IDENT_CDW02, 5)) &&
701           (grub_memcmp (vrs.magic, GRUB_UDF_STD_IDENT_TEA01, 5)))
702         {
703           grub_error (GRUB_ERR_BAD_FS, "not an UDF filesystem");
704           goto fail;
705         }
706     }
707
708   data->npd = data->npm = 0;
709   /* Locate Partition Descriptor (PD) and Logical Volume Descriptor (LVD).  */
710   while (1)
711     {
712       struct grub_udf_tag tag;
713
714       if (grub_disk_read (disk, block << lbshift, 0,
715                           sizeof (struct grub_udf_tag), &tag))
716         {
717           grub_error (GRUB_ERR_BAD_FS, "not an UDF filesystem");
718           goto fail;
719         }
720
721       tag.tag_ident = U16 (tag.tag_ident);
722       if (tag.tag_ident == GRUB_UDF_TAG_IDENT_PVD)
723         {
724           if (grub_disk_read (disk, block << lbshift, 0,
725                               sizeof (struct grub_udf_pvd),
726                               &data->pvd))
727             {
728               grub_error (GRUB_ERR_BAD_FS, "not an UDF filesystem");
729               goto fail;
730             }
731         }
732       else if (tag.tag_ident == GRUB_UDF_TAG_IDENT_PD)
733         {
734           if (data->npd >= GRUB_UDF_MAX_PDS)
735             {
736               grub_error (GRUB_ERR_BAD_FS, "too many PDs");
737               goto fail;
738             }
739
740           if (grub_disk_read (disk, block << lbshift, 0,
741                               sizeof (struct grub_udf_pd),
742                               &data->pds[data->npd]))
743             {
744               grub_error (GRUB_ERR_BAD_FS, "not an UDF filesystem");
745               goto fail;
746             }
747
748           data->npd++;
749         }
750       else if (tag.tag_ident == GRUB_UDF_TAG_IDENT_LVD)
751         {
752           int k;
753
754           struct grub_udf_partmap *ppm;
755
756           if (grub_disk_read (disk, block << lbshift, 0,
757                               sizeof (struct grub_udf_lvd),
758                               &data->lvd))
759             {
760               grub_error (GRUB_ERR_BAD_FS, "not an UDF filesystem");
761               goto fail;
762             }
763
764           if (data->npm + U32 (data->lvd.num_part_maps) > GRUB_UDF_MAX_PMS)
765             {
766               grub_error (GRUB_ERR_BAD_FS, "too many partition maps");
767               goto fail;
768             }
769
770           ppm = (struct grub_udf_partmap *) &data->lvd.part_maps;
771           for (k = U32 (data->lvd.num_part_maps); k > 0; k--)
772             {
773               if (ppm->type != GRUB_UDF_PARTMAP_TYPE_1)
774                 {
775                   grub_error (GRUB_ERR_BAD_FS, "partmap type not supported");
776                   goto fail;
777                 }
778
779               data->pms[data->npm++] = ppm;
780               ppm = (struct grub_udf_partmap *) ((char *) ppm +
781                                                  U32 (ppm->length));
782             }
783         }
784       else if (tag.tag_ident > GRUB_UDF_TAG_IDENT_TD)
785         {
786           grub_error (GRUB_ERR_BAD_FS, "invalid tag ident");
787           goto fail;
788         }
789       else if (tag.tag_ident == GRUB_UDF_TAG_IDENT_TD)
790         break;
791
792       block++;
793     }
794
795   for (i = 0; i < data->npm; i++)
796     {
797       int j;
798
799       for (j = 0; j < data->npd; j++)
800         if (data->pms[i]->type1.part_num == data->pds[j].part_num)
801           {
802             data->pms[i]->type1.part_num = j;
803             break;
804           }
805
806       if (j == data->npd)
807         {
808           grub_error (GRUB_ERR_BAD_FS, "can\'t find PD");
809           goto fail;
810         }
811     }
812
813   block = grub_udf_get_block (data,
814                               data->lvd.root_fileset.block.part_ref,
815                               data->lvd.root_fileset.block.block_num);
816
817   if (grub_errno)
818     goto fail;
819
820   if (grub_disk_read (disk, block << lbshift, 0,
821                       sizeof (struct grub_udf_fileset), &root_fs))
822     {
823       grub_error (GRUB_ERR_BAD_FS, "not an UDF filesystem");
824       goto fail;
825     }
826
827   if (U16 (root_fs.tag.tag_ident) != GRUB_UDF_TAG_IDENT_FSD)
828     {
829       grub_error (GRUB_ERR_BAD_FS, "invalid fileset descriptor");
830       goto fail;
831     }
832
833   data->root_icb = root_fs.root_icb;
834
835   return data;
836
837 fail:
838   grub_free (data);
839   return 0;
840 }
841
842 #ifdef GRUB_UTIL
843 grub_disk_addr_t
844 grub_udf_get_cluster_sector (grub_disk_t disk, grub_uint64_t *sec_per_lcn)
845 {
846   grub_disk_addr_t ret;
847   static struct grub_udf_data *data;
848
849   data = grub_udf_mount (disk);
850   if (!data)
851     return 0;
852
853   ret = U32 (data->pds[data->pms[0]->type1.part_num].start);
854   *sec_per_lcn = 1ULL << data->lbshift;
855   grub_free (data);
856   return ret;
857 }
858 #endif
859
860 static char *
861 read_string (const grub_uint8_t *raw, grub_size_t sz, char *outbuf)
862 {
863   grub_uint16_t *utf16 = NULL;
864   grub_size_t utf16len = 0;
865
866   if (sz == 0)
867     return NULL;
868
869   if (raw[0] != 8 && raw[0] != 16)
870     return NULL;
871
872   if (raw[0] == 8)
873     {
874       unsigned i;
875       utf16len = sz - 1;
876       utf16 = grub_malloc (utf16len * sizeof (utf16[0]));
877       if (!utf16)
878         return NULL;
879       for (i = 0; i < utf16len; i++)
880         utf16[i] = raw[i + 1];
881     }
882   if (raw[0] == 16)
883     {
884       unsigned i;
885       utf16len = (sz - 1) / 2;
886       utf16 = grub_malloc (utf16len * sizeof (utf16[0]));
887       if (!utf16)
888         return NULL;
889       for (i = 0; i < utf16len; i++)
890         utf16[i] = (raw[2 * i + 1] << 8) | raw[2*i + 2];
891     }
892   if (!outbuf)
893     outbuf = grub_malloc (utf16len * GRUB_MAX_UTF8_PER_UTF16 + 1);
894   if (outbuf)
895     *grub_utf16_to_utf8 ((grub_uint8_t *) outbuf, utf16, utf16len) = '\0';
896   grub_free (utf16);
897   return outbuf;
898 }
899
900 static char *
901 read_dstring (const grub_uint8_t *raw, grub_size_t sz)
902 {
903   grub_size_t len;
904
905   if (raw[0] == 0) {
906       char *outbuf = grub_malloc (1);
907       if (!outbuf)
908         return NULL;
909       outbuf[0] = 0;
910       return outbuf;
911     }
912
913   len = raw[sz - 1];
914   if (len > sz - 1)
915     len = sz - 1;
916   return read_string (raw, len, NULL);
917 }
918
919 static int
920 grub_udf_iterate_dir (grub_fshelp_node_t dir,
921                       grub_fshelp_iterate_dir_hook_t hook, void *hook_data)
922 {
923   grub_fshelp_node_t child;
924   struct grub_udf_file_ident dirent;
925   grub_off_t offset = 0;
926
927   child = grub_malloc (get_fshelp_size (dir->data));
928   if (!child)
929     return 0;
930
931   /* The current directory is not stored.  */
932   grub_memcpy (child, dir, get_fshelp_size (dir->data));
933
934   if (hook (".", GRUB_FSHELP_DIR, child, hook_data))
935     return 1;
936
937   while (offset < U64 (dir->block.fe.file_size))
938     {
939       if (grub_udf_read_file (dir, 0, 0, offset, sizeof (dirent),
940                               (char *) &dirent) != sizeof (dirent))
941         return 0;
942
943       if (U16 (dirent.tag.tag_ident) != GRUB_UDF_TAG_IDENT_FID)
944         {
945           grub_error (GRUB_ERR_BAD_FS, "invalid fid tag");
946           return 0;
947         }
948
949       offset += sizeof (dirent) + U16 (dirent.imp_use_length);
950       if (!(dirent.characteristics & GRUB_UDF_FID_CHAR_DELETED))
951         {
952           child = grub_malloc (get_fshelp_size (dir->data));
953           if (!child)
954             return 0;
955
956           if (grub_udf_read_icb (dir->data, &dirent.icb, child))
957             return 0;
958
959           if (dirent.characteristics & GRUB_UDF_FID_CHAR_PARENT)
960             {
961               /* This is the parent directory.  */
962               if (hook ("..", GRUB_FSHELP_DIR, child, hook_data))
963                 return 1;
964             }
965           else
966             {
967               enum grub_fshelp_filetype type;
968               char *filename;
969               grub_uint8_t raw[MAX_FILE_IDENT_LENGTH];
970
971               type = ((dirent.characteristics & GRUB_UDF_FID_CHAR_DIRECTORY) ?
972                       (GRUB_FSHELP_DIR) : (GRUB_FSHELP_REG));
973               if (child->block.fe.icbtag.file_type == GRUB_UDF_ICBTAG_TYPE_SYMLINK)
974                 type = GRUB_FSHELP_SYMLINK;
975
976               if ((grub_udf_read_file (dir, 0, 0, offset,
977                                        dirent.file_ident_length,
978                                        (char *) raw))
979                   != dirent.file_ident_length)
980                 return 0;
981
982               filename = read_string (raw, dirent.file_ident_length, 0);
983               if (!filename)
984                 grub_print_error ();
985
986               if (filename && hook (filename, type, child, hook_data))
987                 {
988                   grub_free (filename);
989                   return 1;
990                 }
991               grub_free (filename);
992             }
993         }
994
995       /* Align to dword boundary.  */
996       offset = (offset + dirent.file_ident_length + 3) & (~3);
997     }
998
999   return 0;
1000 }
1001
1002 static char *
1003 grub_udf_read_symlink (grub_fshelp_node_t node)
1004 {
1005   grub_size_t sz = U64 (node->block.fe.file_size);
1006   grub_uint8_t *raw;
1007   const grub_uint8_t *ptr;
1008   char *out, *optr;
1009
1010   if (sz < 4)
1011     return NULL;
1012   raw = grub_malloc (sz);
1013   if (!raw)
1014     return NULL;
1015   if (grub_udf_read_file (node, NULL, NULL, 0, sz, (char *) raw) < 0)
1016     {
1017       grub_free (raw);
1018       return NULL;
1019     }
1020
1021   out = grub_malloc (sz * 2 + 1);
1022   if (!out)
1023     {
1024       grub_free (raw);
1025       return NULL;
1026     }
1027
1028   optr = out;
1029
1030   for (ptr = raw; ptr < raw + sz; )
1031     {
1032       grub_size_t s;
1033       if ((grub_size_t) (ptr - raw + 4) > sz)
1034         goto fail;
1035       if (!(ptr[2] == 0 && ptr[3] == 0))
1036         goto fail;
1037       s = 4 + ptr[1];
1038       if ((grub_size_t) (ptr - raw + s) > sz)
1039         goto fail;
1040       switch (*ptr)
1041         {
1042         case 1:
1043           if (ptr[1])
1044             goto fail;
1045           /* Fallthrough.  */
1046         case 2:
1047           /* in 4 bytes. out: 1 byte.  */
1048           optr = out;
1049           *optr++ = '/';
1050           break;
1051         case 3:
1052           /* in 4 bytes. out: 3 bytes.  */
1053           if (optr != out)
1054             *optr++ = '/';
1055           *optr++ = '.';
1056           *optr++ = '.';
1057           break;
1058         case 4:
1059           /* in 4 bytes. out: 2 bytes.  */
1060           if (optr != out)
1061             *optr++ = '/';
1062           *optr++ = '.';
1063           break;
1064         case 5:
1065           /* in 4 + n bytes. out, at most: 1 + 2 * n bytes.  */
1066           if (optr != out)
1067             *optr++ = '/';
1068           if (!read_string (ptr + 4, s - 4, optr))
1069             goto fail;
1070           optr += grub_strlen (optr);
1071           break;
1072         default:
1073           goto fail;
1074         }
1075       ptr += s;
1076     }
1077   *optr = 0;
1078   grub_free (raw);
1079   return out;
1080
1081  fail:
1082   grub_free (raw);
1083   grub_free (out);
1084   grub_error (GRUB_ERR_BAD_FS, "invalid symlink");
1085   return NULL;
1086 }
1087
1088 /* Context for grub_udf_dir.  */
1089 struct grub_udf_dir_ctx
1090 {
1091   grub_fs_dir_hook_t hook;
1092   void *hook_data;
1093 };
1094
1095 /* Helper for grub_udf_dir.  */
1096 static int
1097 grub_udf_dir_iter (const char *filename, enum grub_fshelp_filetype filetype,
1098                    grub_fshelp_node_t node, void *data)
1099 {
1100   struct grub_udf_dir_ctx *ctx = data;
1101   struct grub_dirhook_info info;
1102   const struct grub_udf_timestamp *tstamp = NULL;
1103
1104   grub_memset (&info, 0, sizeof (info));
1105   info.dir = ((filetype & GRUB_FSHELP_TYPE_MASK) == GRUB_FSHELP_DIR);
1106   if (U16 (node->block.fe.tag.tag_ident) == GRUB_UDF_TAG_IDENT_FE)
1107     tstamp = &node->block.fe.modification_time;
1108   else if (U16 (node->block.fe.tag.tag_ident) == GRUB_UDF_TAG_IDENT_EFE)
1109     tstamp = &node->block.efe.modification_time;
1110
1111   if (tstamp && (U16 (tstamp->type_and_timezone) & 0xf000) == 0x1000)
1112     {
1113       grub_int16_t tz;
1114       struct grub_datetime datetime;
1115
1116       datetime.year = U16 (tstamp->year);
1117       datetime.month = tstamp->month;
1118       datetime.day = tstamp->day;
1119       datetime.hour = tstamp->hour;
1120       datetime.minute = tstamp->minute;
1121       datetime.second = tstamp->second;
1122
1123       tz = U16 (tstamp->type_and_timezone) & 0xfff;
1124       if (tz & 0x800)
1125         tz |= 0xf000;
1126       if (tz == -2047)
1127         tz = 0;
1128
1129       info.mtimeset = !!grub_datetime2unixtime (&datetime, &info.mtime);
1130
1131       info.mtime -= 60 * tz;
1132     }
1133   grub_free (node);
1134   return ctx->hook (filename, &info, ctx->hook_data);
1135 }
1136
1137 static grub_err_t
1138 grub_udf_dir (grub_device_t device, const char *path,
1139               grub_fs_dir_hook_t hook, void *hook_data)
1140 {
1141   struct grub_udf_dir_ctx ctx = { hook, hook_data };
1142   struct grub_udf_data *data = 0;
1143   struct grub_fshelp_node *rootnode = 0;
1144   struct grub_fshelp_node *foundnode = 0;
1145
1146   grub_dl_ref (my_mod);
1147
1148   data = grub_udf_mount (device->disk);
1149   if (!data)
1150     goto fail;
1151
1152   rootnode = grub_malloc (get_fshelp_size (data));
1153   if (!rootnode)
1154     goto fail;
1155
1156   if (grub_udf_read_icb (data, &data->root_icb, rootnode))
1157     goto fail;
1158
1159   if (grub_fshelp_find_file (path, rootnode,
1160                              &foundnode,
1161                              grub_udf_iterate_dir, grub_udf_read_symlink,
1162                              GRUB_FSHELP_DIR))
1163     goto fail;
1164
1165   grub_udf_iterate_dir (foundnode, grub_udf_dir_iter, &ctx);
1166
1167   if (foundnode != rootnode)
1168     grub_free (foundnode);
1169
1170 fail:
1171   grub_free (rootnode);
1172
1173   grub_free (data);
1174
1175   grub_dl_unref (my_mod);
1176
1177   return grub_errno;
1178 }
1179
1180 static grub_err_t
1181 grub_udf_open (struct grub_file *file, const char *name)
1182 {
1183   struct grub_udf_data *data;
1184   struct grub_fshelp_node *rootnode = 0;
1185   struct grub_fshelp_node *foundnode;
1186
1187   grub_dl_ref (my_mod);
1188
1189   data = grub_udf_mount (file->device->disk);
1190   if (!data)
1191     goto fail;
1192
1193   rootnode = grub_malloc (get_fshelp_size (data));
1194   if (!rootnode)
1195     goto fail;
1196
1197   if (grub_udf_read_icb (data, &data->root_icb, rootnode))
1198     goto fail;
1199
1200   if (grub_fshelp_find_file (name, rootnode,
1201                              &foundnode,
1202                              grub_udf_iterate_dir, grub_udf_read_symlink,
1203                              GRUB_FSHELP_REG))
1204     goto fail;
1205
1206   file->data = foundnode;
1207   file->offset = 0;
1208   file->size = U64 (foundnode->block.fe.file_size);
1209
1210   grub_free (rootnode);
1211
1212   return 0;
1213
1214 fail:
1215   grub_dl_unref (my_mod);
1216
1217   grub_free (data);
1218   grub_free (rootnode);
1219
1220   return grub_errno;
1221 }
1222
1223 static grub_ssize_t
1224 grub_udf_read (grub_file_t file, char *buf, grub_size_t len)
1225 {
1226   struct grub_fshelp_node *node = (struct grub_fshelp_node *) file->data;
1227
1228   return grub_udf_read_file (node, file->read_hook, file->read_hook_data,
1229                              file->offset, len, buf);
1230 }
1231
1232 static grub_err_t
1233 grub_udf_close (grub_file_t file)
1234 {
1235   if (file->data)
1236     {
1237       struct grub_fshelp_node *node = (struct grub_fshelp_node *) file->data;
1238
1239       grub_free (node->data);
1240       grub_free (node);
1241     }
1242
1243   grub_dl_unref (my_mod);
1244
1245   return GRUB_ERR_NONE;
1246 }
1247
1248 static grub_err_t
1249 grub_udf_label (grub_device_t device, char **label)
1250 {
1251   struct grub_udf_data *data;
1252   data = grub_udf_mount (device->disk);
1253
1254   if (data)
1255     {
1256       *label = read_dstring (data->lvd.ident, sizeof (data->lvd.ident));
1257       grub_free (data);
1258     }
1259   else
1260     *label = 0;
1261
1262   return grub_errno;
1263 }
1264
1265 static char *
1266 gen_uuid_from_volset (char *volset_ident)
1267 {
1268   grub_size_t i;
1269   grub_size_t len;
1270   grub_size_t nonhexpos;
1271   grub_uint8_t buf[17];
1272   char *uuid;
1273
1274   len = grub_strlen (volset_ident);
1275   if (len < 8)
1276     return NULL;
1277
1278   uuid = grub_malloc (17);
1279   if (!uuid)
1280     return NULL;
1281
1282   if (len > 16)
1283     len = 16;
1284
1285   grub_memset (buf, 0, sizeof (buf));
1286   grub_memcpy (buf, volset_ident, len);
1287
1288   nonhexpos = 16;
1289   for (i = 0; i < 16; ++i)
1290     {
1291       if (!grub_isxdigit (buf[i]))
1292         {
1293           nonhexpos = i;
1294           break;
1295         }
1296     }
1297
1298   if (nonhexpos < 8)
1299     {
1300       grub_snprintf (uuid, 17, "%02x%02x%02x%02x%02x%02x%02x%02x",
1301                     buf[0], buf[1], buf[2], buf[3],
1302                     buf[4], buf[5], buf[6], buf[7]);
1303     }
1304   else if (nonhexpos < 16)
1305     {
1306       for (i = 0; i < 8; ++i)
1307         uuid[i] = grub_tolower (buf[i]);
1308       grub_snprintf (uuid+8, 9, "%02x%02x%02x%02x",
1309                     buf[8], buf[9], buf[10], buf[11]);
1310     }
1311   else
1312     {
1313       for (i = 0; i < 16; ++i)
1314         uuid[i] = grub_tolower (buf[i]);
1315       uuid[16] = 0;
1316     }
1317
1318   return uuid;
1319 }
1320
1321 static grub_err_t
1322 grub_udf_uuid (grub_device_t device, char **uuid)
1323 {
1324   char *volset_ident;
1325   struct grub_udf_data *data;
1326   data = grub_udf_mount (device->disk);
1327
1328   if (data)
1329     {
1330       volset_ident = read_dstring (data->pvd.volset_ident, sizeof (data->pvd.volset_ident));
1331       if (volset_ident)
1332         {
1333           *uuid = gen_uuid_from_volset (volset_ident);
1334           grub_free (volset_ident);
1335         }
1336       else
1337         *uuid = 0;
1338       grub_free (data);
1339     }
1340   else
1341     *uuid = 0;
1342
1343   return grub_errno;
1344 }
1345
1346 static struct grub_fs grub_udf_fs = {
1347   .name = "udf",
1348   .dir = grub_udf_dir,
1349   .open = grub_udf_open,
1350   .read = grub_udf_read,
1351   .close = grub_udf_close,
1352   .label = grub_udf_label,
1353   .uuid = grub_udf_uuid,
1354 #ifdef GRUB_UTIL
1355   .reserved_first_sector = 1,
1356   .blocklist_install = 1,
1357 #endif
1358   .next = 0
1359 };
1360
1361 GRUB_MOD_INIT (udf)
1362 {
1363   grub_fs_register (&grub_udf_fs);
1364   my_mod = mod;
1365 }
1366
1367 GRUB_MOD_FINI (udf)
1368 {
1369   grub_fs_unregister (&grub_udf_fs);
1370 }