1%%% -*- erlang-indent-level: 2 -*-
2%%%
3%%% Licensed under the Apache License, Version 2.0 (the "License");
4%%% you may not use this file except in compliance with the License.
5%%% You may obtain a copy of the License at
6%%%
7%%%     http://www.apache.org/licenses/LICENSE-2.0
8%%%
9%%% Unless required by applicable law or agreed to in writing, software
10%%% distributed under the License is distributed on an "AS IS" BASIS,
11%%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12%%% See the License for the specific language governing permissions and
13%%% limitations under the License.
14%%%
15%%%-------------------------------------------------------------------
16%%% File    : hipe_rtl_binary.erl
17%%% Author  : Per Gustafsson <pergu@it.uu.se>
18%%% Description :
19%%%
20%%% Created : 5 Mar 2007 by Per Gustafsson <pergu@it.uu.se>
21%%%-------------------------------------------------------------------
22-module(hipe_rtl_binary).
23
24-export([gen_rtl/7]).
25
26-export([floorlog2/1, get_word_integer/4, make_size/3, make_size/4]).
27
28%%--------------------------------------------------------------------
29
30-define(BYTE_SHIFT, 3). %% Turn bits into bytes or vice versa
31-define(BYTE_SIZE, 8).
32
33%%--------------------------------------------------------------------
34
35gen_rtl(BsOP, Dst, Args, TrueLblName, FalseLblName, SysLimName, ConstTab) ->
36  case type_of_operation(BsOP) of
37    match ->
38      {hipe_rtl_binary_match:gen_rtl(
39	 BsOP, Dst, Args, TrueLblName, FalseLblName),ConstTab};
40    construct ->
41      hipe_rtl_binary_construct:gen_rtl(
42	BsOP, Dst, Args, TrueLblName, FalseLblName, SysLimName, ConstTab)
43  end.
44
45type_of_operation({bs_start_match,_}) -> match;
46type_of_operation({{bs_start_match,_},_}) -> match;
47type_of_operation({bs_get_binary,_,_}) -> match;
48type_of_operation({bs_get_binary_all,_,_}) -> match;
49type_of_operation({bs_get_binary_all_2,_,_}) -> match;
50type_of_operation({bs_get_integer,_,_}) -> match;
51type_of_operation({bs_get_float,_,_}) ->  match;
52type_of_operation({bs_skip_bits,_}) -> match;
53type_of_operation({bs_skip_bits_all,_,_}) ->  match;
54type_of_operation({bs_test_tail,_}) -> match;
55type_of_operation({bs_restore,_}) -> match;
56type_of_operation({bs_save,_}) ->  match;
57type_of_operation({bs_test_unit,_}) ->  match;
58type_of_operation({bs_match_string,_,_}) ->  match;
59type_of_operation(bs_context_to_binary) ->  match;
60type_of_operation({bs_add,_}) -> construct;
61type_of_operation({bs_add,_,_}) -> construct;
62type_of_operation(bs_bits_to_bytes) -> construct;
63type_of_operation(bs_bits_to_bytes2) -> construct;
64type_of_operation({bs_init,_}) -> construct;
65type_of_operation({bs_init,_,_}) -> construct;
66type_of_operation({bs_init_bits,_}) -> construct;
67type_of_operation({bs_init_bits,_,_}) -> construct;
68type_of_operation({bs_put_binary,_,_}) -> construct;
69type_of_operation({bs_put_binary_all,_,_}) -> construct;
70type_of_operation({bs_put_float,_,_,_}) -> construct;
71type_of_operation({bs_put_integer,_,_,_}) -> construct;
72type_of_operation({bs_put_string,_,_}) -> construct;
73type_of_operation({unsafe_bs_put_integer,_,_,_}) -> construct;
74type_of_operation(bs_utf8_size) -> construct;
75type_of_operation(bs_put_utf8) -> construct;
76type_of_operation(bs_get_utf8) -> match;
77type_of_operation(bs_utf16_size) -> construct;
78type_of_operation({bs_put_utf16,_}) -> construct;
79type_of_operation({bs_get_utf16,_}) -> match;
80type_of_operation(bs_validate_unicode) -> construct;
81type_of_operation(bs_validate_unicode_retract) -> match;
82type_of_operation(bs_final) -> construct;
83type_of_operation({bs_append,_,_,_,_}) -> construct;
84type_of_operation({bs_private_append,_,_}) -> construct;
85type_of_operation(bs_init_writable) -> construct.
86
87%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
88%%
89%% Small utility functions:
90%%
91%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92
93create_lbls(X) when X > 0 ->
94  [hipe_rtl:mk_new_label()|create_lbls(X-1)];
95create_lbls(0) ->
96  [].
97
98%%------------------------------------------------------------------------------
99%% Utilities used by both hipe_rtl_binary_construct and hipe_rtl_binary_match
100%%------------------------------------------------------------------------------
101
102get_word_integer(Var, Register, SystemLimitLblName, FalseLblName) ->
103  case hipe_rtl:is_imm(Var) of
104    true ->
105      TaggedVal = hipe_rtl:imm_value(Var),
106      true = hipe_tagscheme:is_fixnum(TaggedVal),
107      Val = hipe_tagscheme:fixnum_val(TaggedVal),
108      if Val < 0 -> [hipe_rtl:mk_goto(FalseLblName)];
109	true -> [hipe_rtl:mk_move(Register, hipe_rtl:mk_imm(Val))]
110      end;
111    false ->
112      [EndLbl] = create_lbls(1),
113      EndName = hipe_rtl:label_name(EndLbl),
114      get_word_integer(Var, Register,SystemLimitLblName,  FalseLblName,
115		       EndName, EndName, [EndLbl])
116  end.
117
118get_word_integer(Var, Register, SystemLimitLblName, FalseLblName, TrueLblName,
119		 BigLblName, Tail) ->
120  [FixnumLbl, NotFixnumLbl, BignumLbl, SuccessLbl] = create_lbls(4),
121  [hipe_tagscheme:test_fixnum(Var, hipe_rtl:label_name(FixnumLbl),
122			      hipe_rtl:label_name(NotFixnumLbl), 0.99),
123   FixnumLbl,
124   hipe_tagscheme:fixnum_ge(Var, hipe_rtl:mk_imm(hipe_tagscheme:mk_fixnum(0)),
125			    hipe_rtl:label_name(SuccessLbl), FalseLblName,
126			    0.99),
127   SuccessLbl,
128   hipe_tagscheme:untag_fixnum(Register, Var),
129   hipe_rtl:mk_goto(TrueLblName),
130   NotFixnumLbl,
131   hipe_tagscheme:test_pos_bignum_arity(Var, 1, hipe_rtl:label_name(BignumLbl),
132					FalseLblName, SystemLimitLblName, 0.99),
133   BignumLbl,
134   hipe_tagscheme:unsafe_get_one_word_pos_bignum(Register, Var),
135   hipe_rtl:mk_goto(BigLblName) | Tail].
136
137make_size(UnitImm, BitsVar, FailLblName) ->
138  make_size(UnitImm, BitsVar, FailLblName, FailLblName).
139
140make_size(1, BitsVar, OverflowLblName, FalseLblName) ->
141  DstReg = hipe_rtl:mk_new_reg_gcsafe(),
142  {get_word_integer(BitsVar, DstReg, OverflowLblName, FalseLblName), DstReg};
143make_size(?BYTE_SIZE, BitsVar, OverflowLblName, FalseLblName) ->
144  DstReg = hipe_rtl:mk_new_reg_gcsafe(),
145  [FixnumLbl, BignumLbl] = create_lbls(2),
146  WordBits = hipe_rtl_arch:word_size() * ?BYTE_SIZE,
147  FixnumLblName = hipe_rtl:label_name(FixnumLbl),
148  Tail = [BignumLbl,
149	  hipe_rtl:mk_branch(DstReg, 'ltu',
150			     hipe_rtl:mk_imm(1 bsl (WordBits - ?BYTE_SHIFT)),
151			     FixnumLblName, OverflowLblName, 0.99),
152	  FixnumLbl,
153	  hipe_rtl:mk_alu(DstReg, DstReg, sll, hipe_rtl:mk_imm(?BYTE_SHIFT))],
154  Code = get_word_integer(BitsVar, DstReg, OverflowLblName, FalseLblName,
155			  FixnumLblName, hipe_rtl:label_name(BignumLbl), Tail),
156  {Code, DstReg};
157make_size(UnitImm, BitsVar, OverflowLblName, FalseLblName) ->
158  DstReg = hipe_rtl:mk_new_reg_gcsafe(),
159  UnitList = number2list(UnitImm),
160  Code = multiply_code(UnitList, BitsVar, DstReg, OverflowLblName, FalseLblName),
161  {Code, DstReg}.
162
163multiply_code(List=[Head|_Tail], Variable, Result, OverflowLblName,
164	      FalseLblName) ->
165  Test = set_high(Head),
166  Tmp1 = hipe_rtl:mk_new_reg(),
167  SuccessLbl = hipe_rtl:mk_new_label(),
168  Register = hipe_rtl:mk_new_reg(),
169  Code = [hipe_rtl:mk_move(Result, hipe_rtl:mk_imm(0))|
170	  get_word_integer(Variable, Register, OverflowLblName, FalseLblName)]
171    ++
172    [hipe_rtl:mk_alub(Tmp1, Register, 'and', hipe_rtl:mk_imm(Test),
173		      eq, hipe_rtl:label_name(SuccessLbl),
174		      OverflowLblName, 0.99),
175     SuccessLbl],
176  multiply_code(List, Register, Result, OverflowLblName, Tmp1, Code).
177
178multiply_code([ShiftSize|Rest], Register, Result, OverflowLblName, Tmp1,
179	      OldCode) ->
180  SuccessLbl = hipe_rtl:mk_new_label(),
181  Code =
182    OldCode ++
183    [hipe_rtl:mk_alu(Tmp1, Register, sll, hipe_rtl:mk_imm(ShiftSize)),
184     hipe_rtl:mk_alub(Result, Tmp1, 'add', Result, not_overflow,
185		      hipe_rtl:label_name(SuccessLbl), OverflowLblName, 0.99),
186     SuccessLbl],
187  multiply_code(Rest, Register, Result, OverflowLblName, Tmp1, Code);
188multiply_code([], _Register, _Result, _OverflowLblName, _Tmp1, Code) ->
189  Code.
190
191set_high(X) ->
192  WordBits = hipe_rtl_arch:word_size() * ?BYTE_SIZE,
193  set_high(min(X, WordBits), WordBits, 0).
194
195set_high(0, _, Y) ->
196  Y;
197set_high(X, WordBits, Y) ->
198  set_high(X-1, WordBits, Y+(1 bsl (WordBits-X))).
199
200
201number2list(X) when is_integer(X), X >= 0 ->
202  number2list(X, []).
203
204number2list(1, Acc) ->
205  lists:reverse([0|Acc]);
206number2list(0, Acc) ->
207  lists:reverse(Acc);
208number2list(X, Acc) ->
209  F = floorlog2(X),
210  number2list(X-(1 bsl F), [F|Acc]).
211
212floorlog2(X) ->
213  %% Double-precision floats do not have enough precision to make floorlog2
214  %% exact for integers larger than 2^47.
215  Approx = round(math:log(X)/math:log(2)-0.5),
216  floorlog2_refine(X, Approx).
217
218floorlog2_refine(X, Approx) ->
219  if (1 bsl Approx) > X ->
220      floorlog2_refine(X, Approx - 1);
221     (1 bsl (Approx+1)) > X ->
222      Approx;
223     true ->
224      floorlog2_refine(X, Approx + 1)
225  end.
226