2005-06-02 H.J. Lu <hjl@gnu.org>
[binutils.git] / bfd / stabs.c
blobbba4a6d61ed79552b47cee4ab3e6f7bbe525fa11
1 /* Stabs in sections linking support.
2 Copyright 1996, 1997, 1998, 1999, 2000, 2001
3 Free Software Foundation, Inc.
4 Written by Ian Lance Taylor, Cygnus Support.
6 This file is part of BFD, the Binary File Descriptor library.
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
22 /* This file contains support for linking stabs in sections, as used
23 on COFF and ELF. */
25 #include "bfd.h"
26 #include "sysdep.h"
27 #include "libbfd.h"
28 #include "aout/stab_gnu.h"
29 #include "safe-ctype.h"
31 /* Stabs entries use a 12 byte format:
32 4 byte string table index
33 1 byte stab type
34 1 byte stab other field
35 2 byte stab desc field
36 4 byte stab value
37 FIXME: This will have to change for a 64 bit object format.
39 The stabs symbols are divided into compilation units. For the
40 first entry in each unit, the type of 0, the value is the length of
41 the string table for this unit, and the desc field is the number of
42 stabs symbols for this unit. */
44 #define STRDXOFF (0)
45 #define TYPEOFF (4)
46 #define OTHEROFF (5)
47 #define DESCOFF (6)
48 #define VALOFF (8)
49 #define STABSIZE (12)
51 /* A hash table used for header files with N_BINCL entries. */
53 struct stab_link_includes_table
55 struct bfd_hash_table root;
58 /* A linked list of totals that we have found for a particular header
59 file. */
61 struct stab_link_includes_totals
63 struct stab_link_includes_totals *next;
64 bfd_vma total;
67 /* An entry in the header file hash table. */
69 struct stab_link_includes_entry
71 struct bfd_hash_entry root;
72 /* List of totals we have found for this file. */
73 struct stab_link_includes_totals *totals;
76 /* Look up an entry in an the header file hash table. */
78 #define stab_link_includes_lookup(table, string, create, copy) \
79 ((struct stab_link_includes_entry *) \
80 bfd_hash_lookup (&(table)->root, (string), (create), (copy)))
82 /* This structure is used to hold a list of N_BINCL symbols, some of
83 which might be converted into N_EXCL symbols. */
85 struct stab_excl_list
87 /* The next symbol to convert. */
88 struct stab_excl_list *next;
89 /* The offset to this symbol in the section contents. */
90 bfd_size_type offset;
91 /* The value to use for the symbol. */
92 bfd_vma val;
93 /* The type of this symbol (N_BINCL or N_EXCL). */
94 int type;
97 /* This structure is stored with each .stab section. */
99 struct stab_section_info
101 /* This is a linked list of N_BINCL symbols which should be
102 converted into N_EXCL symbols. */
103 struct stab_excl_list *excls;
105 /* This is used to map input stab offsets within their sections
106 to output stab offsets, to take into account stabs that have
107 been deleted. If it is NULL, the output offsets are the same
108 as the input offsets, because no stabs have been deleted from
109 this section. Otherwise the i'th entry is the number of
110 bytes of stabs that have been deleted prior to the i'th
111 stab. */
112 bfd_size_type *cumulative_skips;
114 /* This is an array of string indices. For each stab symbol, we
115 store the string index here. If a stab symbol should not be
116 included in the final output, the string index is -1. */
117 bfd_size_type stridxs[1];
120 /* This structure is used to keep track of stabs in sections
121 information while linking. */
123 struct stab_info
125 /* A hash table used to hold stabs strings. */
126 struct bfd_strtab_hash *strings;
127 /* The header file hash table. */
128 struct stab_link_includes_table includes;
129 /* The first .stabstr section. */
130 asection *stabstr;
133 static struct bfd_hash_entry *stab_link_includes_newfunc
134 PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
136 /* The function to create a new entry in the header file hash table. */
138 static struct bfd_hash_entry *
139 stab_link_includes_newfunc (entry, table, string)
140 struct bfd_hash_entry *entry;
141 struct bfd_hash_table *table;
142 const char *string;
144 struct stab_link_includes_entry *ret =
145 (struct stab_link_includes_entry *) entry;
147 /* Allocate the structure if it has not already been allocated by a
148 subclass. */
149 if (ret == (struct stab_link_includes_entry *) NULL)
150 ret = ((struct stab_link_includes_entry *)
151 bfd_hash_allocate (table,
152 sizeof (struct stab_link_includes_entry)));
153 if (ret == (struct stab_link_includes_entry *) NULL)
154 return (struct bfd_hash_entry *) ret;
156 /* Call the allocation method of the superclass. */
157 ret = ((struct stab_link_includes_entry *)
158 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
159 if (ret)
161 /* Set local fields. */
162 ret->totals = NULL;
165 return (struct bfd_hash_entry *) ret;
168 /* This function is called for each input file from the add_symbols
169 pass of the linker. */
171 boolean
172 _bfd_link_section_stabs (abfd, psinfo, stabsec, stabstrsec, psecinfo)
173 bfd *abfd;
174 PTR *psinfo;
175 asection *stabsec;
176 asection *stabstrsec;
177 PTR *psecinfo;
179 boolean first;
180 struct stab_info *sinfo;
181 bfd_size_type count, amt;
182 struct stab_section_info *secinfo;
183 bfd_byte *stabbuf = NULL;
184 bfd_byte *stabstrbuf = NULL;
185 bfd_byte *sym, *symend;
186 bfd_size_type stroff, next_stroff, skip;
187 bfd_size_type *pstridx;
189 if (stabsec->_raw_size == 0
190 || stabstrsec->_raw_size == 0)
192 /* This file does not contain stabs debugging information. */
193 return true;
196 if (stabsec->_raw_size % STABSIZE != 0)
198 /* Something is wrong with the format of these stab symbols.
199 Don't try to optimize them. */
200 return true;
203 if ((stabstrsec->flags & SEC_RELOC) != 0)
205 /* We shouldn't see relocations in the strings, and we aren't
206 prepared to handle them. */
207 return true;
210 if ((stabsec->output_section != NULL
211 && bfd_is_abs_section (stabsec->output_section))
212 || (stabstrsec->output_section != NULL
213 && bfd_is_abs_section (stabstrsec->output_section)))
215 /* At least one of the sections is being discarded from the
216 link, so we should just ignore them. */
217 return true;
220 first = false;
222 if (*psinfo == NULL)
224 /* Initialize the stabs information we need to keep track of. */
225 first = true;
226 amt = sizeof (struct stab_info);
227 *psinfo = (PTR) bfd_alloc (abfd, amt);
228 if (*psinfo == NULL)
229 goto error_return;
230 sinfo = (struct stab_info *) *psinfo;
231 sinfo->strings = _bfd_stringtab_init ();
232 if (sinfo->strings == NULL)
233 goto error_return;
234 /* Make sure the first byte is zero. */
235 (void) _bfd_stringtab_add (sinfo->strings, "", true, true);
236 if (! bfd_hash_table_init_n (&sinfo->includes.root,
237 stab_link_includes_newfunc,
238 251))
239 goto error_return;
240 sinfo->stabstr = bfd_make_section_anyway (abfd, ".stabstr");
241 sinfo->stabstr->flags |= SEC_HAS_CONTENTS | SEC_READONLY | SEC_DEBUGGING;
244 sinfo = (struct stab_info *) *psinfo;
246 /* Initialize the information we are going to store for this .stab
247 section. */
249 count = stabsec->_raw_size / STABSIZE;
251 amt = sizeof (struct stab_section_info);
252 amt += (count - 1) * sizeof (bfd_size_type);
253 *psecinfo = bfd_alloc (abfd, amt);
254 if (*psecinfo == NULL)
255 goto error_return;
257 secinfo = (struct stab_section_info *) *psecinfo;
258 secinfo->excls = NULL;
259 secinfo->cumulative_skips = NULL;
260 memset (secinfo->stridxs, 0, (size_t) count * sizeof (bfd_size_type));
262 /* Read the stabs information from abfd. */
264 stabbuf = (bfd_byte *) bfd_malloc (stabsec->_raw_size);
265 stabstrbuf = (bfd_byte *) bfd_malloc (stabstrsec->_raw_size);
266 if (stabbuf == NULL || stabstrbuf == NULL)
267 goto error_return;
269 if (! bfd_get_section_contents (abfd, stabsec, stabbuf, (bfd_vma) 0,
270 stabsec->_raw_size)
271 || ! bfd_get_section_contents (abfd, stabstrsec, stabstrbuf, (bfd_vma) 0,
272 stabstrsec->_raw_size))
273 goto error_return;
275 /* Look through the stabs symbols, work out the new string indices,
276 and identify N_BINCL symbols which can be eliminated. */
278 stroff = 0;
279 next_stroff = 0;
280 skip = 0;
282 symend = stabbuf + stabsec->_raw_size;
283 for (sym = stabbuf, pstridx = secinfo->stridxs;
284 sym < symend;
285 sym += STABSIZE, ++pstridx)
287 int type;
288 const char *string;
290 if (*pstridx != 0)
292 /* This symbol has already been handled by an N_BINCL pass. */
293 continue;
296 type = sym[TYPEOFF];
298 if (type == 0)
300 /* Special type 0 stabs indicate the offset to the next
301 string table. We only copy the very first one. */
302 stroff = next_stroff;
303 next_stroff += bfd_get_32 (abfd, sym + 8);
304 if (! first)
306 *pstridx = (bfd_size_type) -1;
307 ++skip;
308 continue;
310 first = false;
313 /* Store the string in the hash table, and record the index. */
314 string = ((char *) stabstrbuf
315 + stroff
316 + bfd_get_32 (abfd, sym + STRDXOFF));
317 *pstridx = _bfd_stringtab_add (sinfo->strings, string, true, true);
319 /* An N_BINCL symbol indicates the start of the stabs entries
320 for a header file. We need to scan ahead to the next N_EINCL
321 symbol, ignoring nesting, adding up all the characters in the
322 symbol names, not including the file numbers in types (the
323 first number after an open parenthesis). */
324 if (type == N_BINCL)
326 bfd_vma val;
327 int nest;
328 bfd_byte *incl_sym;
329 struct stab_link_includes_entry *incl_entry;
330 struct stab_link_includes_totals *t;
331 struct stab_excl_list *ne;
333 val = 0;
334 nest = 0;
335 for (incl_sym = sym + STABSIZE;
336 incl_sym < symend;
337 incl_sym += STABSIZE)
339 int incl_type;
341 incl_type = incl_sym[TYPEOFF];
342 if (incl_type == 0)
343 break;
344 else if (incl_type == N_EINCL)
346 if (nest == 0)
347 break;
348 --nest;
350 else if (incl_type == N_BINCL)
351 ++nest;
352 else if (nest == 0)
354 const char *str;
356 str = ((char *) stabstrbuf
357 + stroff
358 + bfd_get_32 (abfd, incl_sym + STRDXOFF));
359 for (; *str != '\0'; str++)
361 val += *str;
362 if (*str == '(')
364 /* Skip the file number. */
365 ++str;
366 while (ISDIGIT (*str))
367 ++str;
368 --str;
374 /* If we have already included a header file with the same
375 value, then replaced this one with an N_EXCL symbol. */
376 incl_entry = stab_link_includes_lookup (&sinfo->includes, string,
377 true, true);
378 if (incl_entry == NULL)
379 goto error_return;
381 for (t = incl_entry->totals; t != NULL; t = t->next)
382 if (t->total == val)
383 break;
385 /* Record this symbol, so that we can set the value
386 correctly. */
387 amt = sizeof *ne;
388 ne = (struct stab_excl_list *) bfd_alloc (abfd, amt);
389 if (ne == NULL)
390 goto error_return;
391 ne->offset = sym - stabbuf;
392 ne->val = val;
393 ne->type = N_BINCL;
394 ne->next = secinfo->excls;
395 secinfo->excls = ne;
397 if (t == NULL)
399 /* This is the first time we have seen this header file
400 with this set of stabs strings. */
401 t = ((struct stab_link_includes_totals *)
402 bfd_hash_allocate (&sinfo->includes.root, sizeof *t));
403 if (t == NULL)
404 goto error_return;
405 t->total = val;
406 t->next = incl_entry->totals;
407 incl_entry->totals = t;
409 else
411 bfd_size_type *incl_pstridx;
413 /* We have seen this header file before. Tell the final
414 pass to change the type to N_EXCL. */
415 ne->type = N_EXCL;
417 /* Mark the skipped symbols. */
419 nest = 0;
420 for (incl_sym = sym + STABSIZE, incl_pstridx = pstridx + 1;
421 incl_sym < symend;
422 incl_sym += STABSIZE, ++incl_pstridx)
424 int incl_type;
426 incl_type = incl_sym[TYPEOFF];
428 if (incl_type == N_EINCL)
430 if (nest == 0)
432 *incl_pstridx = (bfd_size_type) -1;
433 ++skip;
434 break;
436 --nest;
438 else if (incl_type == N_BINCL)
439 ++nest;
440 else if (nest == 0)
442 *incl_pstridx = (bfd_size_type) -1;
443 ++skip;
450 free (stabbuf);
451 stabbuf = NULL;
452 free (stabstrbuf);
453 stabstrbuf = NULL;
455 /* We need to set the section sizes such that the linker will
456 compute the output section sizes correctly. We set the .stab
457 size to not include the entries we don't want. We set
458 SEC_EXCLUDE for the .stabstr section, so that it will be dropped
459 from the link. We record the size of the strtab in the first
460 .stabstr section we saw, and make sure we don't set SEC_EXCLUDE
461 for that section. */
462 stabsec->_cooked_size = (count - skip) * STABSIZE;
463 if (stabsec->_cooked_size == 0)
464 stabsec->flags |= SEC_EXCLUDE;
465 stabstrsec->flags |= SEC_EXCLUDE;
466 sinfo->stabstr->_cooked_size = _bfd_stringtab_size (sinfo->strings);
468 /* Calculate the `cumulative_skips' array now that stabs have been
469 deleted for this section. */
471 if (skip != 0)
473 bfd_size_type i, offset;
474 bfd_size_type *pskips;
476 amt = count * sizeof (bfd_size_type);
477 secinfo->cumulative_skips = (bfd_size_type *) bfd_alloc (abfd, amt);
478 if (secinfo->cumulative_skips == NULL)
479 goto error_return;
481 pskips = secinfo->cumulative_skips;
482 pstridx = secinfo->stridxs;
483 offset = 0;
485 for (i = 0; i < count; i++, pskips++, pstridx++)
487 *pskips = offset;
488 if (*pstridx == (bfd_size_type) -1)
489 offset += STABSIZE;
492 BFD_ASSERT (offset != 0);
495 return true;
497 error_return:
498 if (stabbuf != NULL)
499 free (stabbuf);
500 if (stabstrbuf != NULL)
501 free (stabstrbuf);
502 return false;
506 /* This function is called for each input file before the stab
507 section is relocated. It discards stab entries for discarded
508 functions and variables. The function returns true iff
509 any entries have been deleted.
512 boolean
513 _bfd_discard_section_stabs (abfd, stabsec, psecinfo,
514 reloc_symbol_deleted_p, cookie)
515 bfd *abfd;
516 asection *stabsec;
517 PTR psecinfo;
518 boolean (*reloc_symbol_deleted_p) PARAMS ((bfd_vma, PTR));
519 PTR cookie;
521 bfd_size_type count, amt;
522 struct stab_section_info *secinfo;
523 bfd_byte *stabbuf = NULL;
524 bfd_byte *sym, *symend;
525 bfd_size_type skip;
526 bfd_size_type *pstridx;
527 int deleting;
529 if (stabsec->_raw_size == 0)
531 /* This file does not contain stabs debugging information. */
532 return false;
535 if (stabsec->_raw_size % STABSIZE != 0)
537 /* Something is wrong with the format of these stab symbols.
538 Don't try to optimize them. */
539 return false;
542 if ((stabsec->output_section != NULL
543 && bfd_is_abs_section (stabsec->output_section)))
545 /* At least one of the sections is being discarded from the
546 link, so we should just ignore them. */
547 return false;
550 /* We should have initialized our data in _bfd_link_stab_sections.
551 If there was some bizarre error reading the string sections, though,
552 we might not have. Bail rather than asserting. */
553 if (psecinfo == NULL)
554 return false;
556 count = stabsec->_raw_size / STABSIZE;
557 secinfo = (struct stab_section_info *) psecinfo;
559 /* Read the stabs information from abfd. */
561 stabbuf = (bfd_byte *) bfd_malloc (stabsec->_raw_size);
562 if (stabbuf == NULL)
563 goto error_return;
565 if (! bfd_get_section_contents (abfd, stabsec, stabbuf, (bfd_vma) 0,
566 stabsec->_raw_size))
567 goto error_return;
569 /* Look through the stabs symbols and discard any information for
570 discarded functions. */
572 skip = 0;
573 deleting = -1;
575 symend = stabbuf + stabsec->_raw_size;
576 for (sym = stabbuf, pstridx = secinfo->stridxs;
577 sym < symend;
578 sym += STABSIZE, ++pstridx)
580 int type;
582 if (*pstridx == (bfd_size_type) -1)
584 /* This stab was deleted in a previous pass. */
585 continue;
588 type = sym[TYPEOFF];
590 if (type == N_FUN)
592 int strx = bfd_get_32 (abfd, sym + STRDXOFF);
594 if (strx == 0)
596 if (deleting)
598 skip++;
599 *pstridx = -1;
601 deleting = -1;
602 continue;
604 deleting = 0;
605 if ((*reloc_symbol_deleted_p) (sym + VALOFF - stabbuf, cookie))
606 deleting = 1;
609 if (deleting == 1)
611 *pstridx = -1;
612 skip++;
614 else if (deleting == -1)
616 /* Outside of a function. Check for deleted variables. */
617 if (type == N_STSYM || type == N_LCSYM)
618 if ((*reloc_symbol_deleted_p) (sym + VALOFF - stabbuf, cookie))
620 *pstridx = -1;
621 skip ++;
623 /* We should also check for N_GSYM entries which reference a
624 deleted global, but those are less harmful to debuggers
625 and would require parsing the stab strings. */
629 free (stabbuf);
630 stabbuf = NULL;
632 /* Shrink the stabsec as needed. */
633 stabsec->_cooked_size -= skip * STABSIZE;
634 if (stabsec->_cooked_size == 0)
635 stabsec->flags |= SEC_EXCLUDE;
637 /* Recalculate the `cumulative_skips' array now that stabs have been
638 deleted for this section. */
640 if (skip != 0)
642 bfd_size_type i, offset;
643 bfd_size_type *pskips;
645 if (secinfo->cumulative_skips == NULL)
647 amt = count * sizeof (bfd_size_type);
648 secinfo->cumulative_skips = (bfd_size_type *) bfd_alloc (abfd, amt);
649 if (secinfo->cumulative_skips == NULL)
650 goto error_return;
653 pskips = secinfo->cumulative_skips;
654 pstridx = secinfo->stridxs;
655 offset = 0;
657 for (i = 0; i < count; i++, pskips++, pstridx++)
659 *pskips = offset;
660 if (*pstridx == (bfd_size_type) -1)
661 offset += STABSIZE;
664 BFD_ASSERT (offset != 0);
667 return (skip > 0);
669 error_return:
670 if (stabbuf != NULL)
671 free (stabbuf);
672 return false;
675 /* Write out the stab section. This is called with the relocated
676 contents. */
678 boolean
679 _bfd_write_section_stabs (output_bfd, psinfo, stabsec, psecinfo, contents)
680 bfd *output_bfd;
681 PTR *psinfo;
682 asection *stabsec;
683 PTR *psecinfo;
684 bfd_byte *contents;
686 struct stab_info *sinfo;
687 struct stab_section_info *secinfo;
688 struct stab_excl_list *e;
689 bfd_byte *sym, *tosym, *symend;
690 bfd_size_type *pstridx;
692 sinfo = (struct stab_info *) *psinfo;
693 secinfo = (struct stab_section_info *) *psecinfo;
695 if (secinfo == NULL)
696 return bfd_set_section_contents (output_bfd, stabsec->output_section,
697 contents,
698 (file_ptr) stabsec->output_offset,
699 stabsec->_raw_size);
701 /* Handle each N_BINCL entry. */
702 for (e = secinfo->excls; e != NULL; e = e->next)
704 bfd_byte *excl_sym;
706 BFD_ASSERT (e->offset < stabsec->_raw_size);
707 excl_sym = contents + e->offset;
708 bfd_put_32 (output_bfd, e->val, excl_sym + VALOFF);
709 excl_sym[TYPEOFF] = e->type;
712 /* Copy over all the stabs symbols, omitting the ones we don't want,
713 and correcting the string indices for those we do want. */
714 tosym = contents;
715 symend = contents + stabsec->_raw_size;
716 for (sym = contents, pstridx = secinfo->stridxs;
717 sym < symend;
718 sym += STABSIZE, ++pstridx)
720 if (*pstridx != (bfd_size_type) -1)
722 if (tosym != sym)
723 memcpy (tosym, sym, STABSIZE);
724 bfd_put_32 (output_bfd, *pstridx, tosym + STRDXOFF);
726 if (sym[TYPEOFF] == 0)
728 /* This is the header symbol for the stabs section. We
729 don't really need one, since we have merged all the
730 input stabs sections into one, but we generate one
731 for the benefit of readers which expect to see one. */
732 BFD_ASSERT (sym == contents);
733 bfd_put_32 (output_bfd, _bfd_stringtab_size (sinfo->strings),
734 tosym + VALOFF);
735 bfd_put_16 (output_bfd,
736 stabsec->output_section->_raw_size / STABSIZE - 1,
737 tosym + DESCOFF);
740 tosym += STABSIZE;
744 BFD_ASSERT ((bfd_size_type) (tosym - contents) == stabsec->_cooked_size);
746 return bfd_set_section_contents (output_bfd, stabsec->output_section,
747 contents, (file_ptr) stabsec->output_offset,
748 stabsec->_cooked_size);
751 /* Write out the .stabstr section. */
753 boolean
754 _bfd_write_stab_strings (output_bfd, psinfo)
755 bfd *output_bfd;
756 PTR *psinfo;
758 struct stab_info *sinfo;
760 sinfo = (struct stab_info *) *psinfo;
762 if (sinfo == NULL)
763 return true;
765 if (bfd_is_abs_section (sinfo->stabstr->output_section))
767 /* The section was discarded from the link. */
768 return true;
771 BFD_ASSERT ((sinfo->stabstr->output_offset
772 + _bfd_stringtab_size (sinfo->strings))
773 <= sinfo->stabstr->output_section->_raw_size);
775 if (bfd_seek (output_bfd,
776 (file_ptr) (sinfo->stabstr->output_section->filepos
777 + sinfo->stabstr->output_offset),
778 SEEK_SET) != 0)
779 return false;
781 if (! _bfd_stringtab_emit (output_bfd, sinfo->strings))
782 return false;
784 /* We no longer need the stabs information. */
785 _bfd_stringtab_free (sinfo->strings);
786 bfd_hash_table_free (&sinfo->includes.root);
788 return true;
791 /* Adjust an address in the .stab section. Given OFFSET within
792 STABSEC, this returns the new offset in the adjusted stab section,
793 or -1 if the address refers to a stab which has been removed. */
795 bfd_vma
796 _bfd_stab_section_offset (output_bfd, psinfo, stabsec, psecinfo, offset)
797 bfd *output_bfd ATTRIBUTE_UNUSED;
798 PTR *psinfo ATTRIBUTE_UNUSED;
799 asection *stabsec;
800 PTR *psecinfo;
801 bfd_vma offset;
803 struct stab_section_info *secinfo;
805 secinfo = (struct stab_section_info *) *psecinfo;
807 if (secinfo == NULL)
808 return offset;
810 if (offset >= stabsec->_raw_size)
811 return offset - (stabsec->_cooked_size - stabsec->_raw_size);
813 if (secinfo->cumulative_skips)
815 bfd_vma i;
817 i = offset / STABSIZE;
819 if (secinfo->stridxs [i] == (bfd_size_type) -1)
820 return (bfd_vma) -1;
822 return offset - secinfo->cumulative_skips [i];
825 return offset;